Теория сложности (старая трешовая версия) — различия между версиями
(Отмена правки 1338 участника 192.168.0.2 (обсуждение)) |
Akhi (обсуждение | вклад) |
||
| Строка 94: | Строка 94: | ||
*[[Кубит]] | *[[Кубит]] | ||
*[[Унитарные операторы]] | *[[Унитарные операторы]] | ||
| + | *[[ЭПР парадокс]] | ||
*[[Квантовый логический элемент NOT]] | *[[Квантовый логический элемент NOT]] | ||
*[[Преобразование Адамара]] | *[[Преобразование Адамара]] | ||
Версия 14:54, 2 июня 2010
Содержание
Лекция 1
- Класс DSPACE
- Класс DTIME
- Теорема о емкостной иерархии
- Теорема о временной иерархии
- Сведение по Карпу
- Сведение по Куку
- Класс P
- Класс NP
- Класс coNP
Практика 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
- Квантовый логический элемент Тоффоли
- Квантовая схема
