Теория сложности (старая трешовая версия) — различия между версиями
Ulyantsev (обсуждение | вклад) (→Лекция 1. Вводная) |
Ulyantsev (обсуждение | вклад) (→Лекция 1. Вводная) |
||
| Строка 2: | Строка 2: | ||
Курс начинается с введения понятий '''[[Класс DSPACE |DSPACE]]''' и '''[[Класс DTIME |DTIME]]'''. | Курс начинается с введения понятий '''[[Класс DSPACE |DSPACE]]''' и '''[[Класс DTIME |DTIME]]'''. | ||
| − | '''DTIME'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Time(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> — длина входа <tex>x</tex>. | + | *'''DTIME'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Time(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> — длина входа <tex>x</tex>. |
| − | '''DSPACE'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Space(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> — длина входа <tex>x</tex>. | + | *'''DSPACE'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Space(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> — длина входа <tex>x</tex>. |
| + | Были рассмотрены и доказаны теоремы о емкостной и временной иерархии. | ||
| + | *[[Теорема о емкостной иерархии]] утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется '''DSPACE'''(''g''(''n'')) ≠ '''DSPACE'''(''f''(''n'')). | ||
Через эти классы будет дано определение многим сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''. | Через эти классы будет дано определение многим сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''. | ||
| − | |||
*[[Теорема о временной иерархии]] | *[[Теорема о временной иерархии]] | ||
*[[Класс co-NP]] | *[[Класс co-NP]] | ||
Версия 18:32, 2 июня 2010
Содержание
Лекция 1. Вводная
Курс начинается с введения понятий DSPACE и DTIME.
- DTIME(f(n)) = машина Тьюринга , где — длина входа .
- DSPACE(f(n)) = машина Тьюринга , где — длина входа .
Были рассмотрены и доказаны теоремы о емкостной и временной иерархии.
- Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций и таких, что , выполняется DSPACE(g(n)) ≠ DSPACE(f(n)).
Через эти классы будет дано определение многим сложностным классам, в том числе P и NP.
Практика 1
Лекция 2
Практика 2
- Понятие NP-трудной и NP-полной задачи
- NP-полнота задачи BH1N
- NP-полнота задачи о выполнимости булевой формулы в форме КНФ
- NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
- NP-полнота задачи о клике
- NP-полнота задачи о независимом множестве
- NP-полнота задачи о вершинном покрытии
Лекция 3
Практика 3
- NP-полнота задач о гамильтоновом цикле и пути в графах
- NP-полнота задачи о сумме подмножества
- NP-полнота задачи о рюкзаке
Практика, которой на самом деле не было
Лекция 5
Лекция 6
- Классы L, NL, NLC
- NL-полнота задачи о достижимости в графе
- Классы EXP, NEXP. Полнота языков EXP и NEXP
- Теорема о связи вопросов EXP=NEXP и P=NP
- Теорема Иммермана
Практика 6
Лекция 7
Практика 7
- Вероятностная машина Тьюринга
- Класс ZPP
- Сложностные классы RP и coRP
- Сложностный класс PP
- Сложностный класс BPP
- Уменьшение ошибки в классе RP, сильное и слабое определение
Лекция 8
Практика 8
Лекция 9
Лекция 10
Лекция 11
- Абсолютная секретность
- Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
- Односторонние функции и псевдослучайные генераторы
- Доказательства с нулевым разглашением
Лекция 12
- Кубит
- Унитарные операторы
- ЭПР парадокс
- Квантовый логический элемент NOT
- Преобразование Адамара
- Квантовый логический элемент CNOT
- Квантовый логический элемент Тоффоли
- Квантовая схема
