Изменения
→Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ===== Базовые определения ===*[[Категория: Теория сложностиСложностные классы]]*[[Вычисления с оракулом]]
*[[Класс P]]
*[[Недетерминированные вычисления. ]]*[[Классы NP и , coNP, Σ₁, Π₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Примеры Сведение по Куку задачи факторизации к языку из NP]]*[[NP-полных языков. полнота BH1N]]*[[Теорема Кука]]
*[[Теоремы о временной и емкостной иерархиях]]
*[[Теорема Бейкера — Гилла — Соловэя]]
*[[Теорема Бермана — Форчуна]]
*[[Теорема Махэни]]
=== [[Примеры NP-полных языков]] ===* [[NP-полнота языка CNFSAT]]* [[NP-полнота языка 3SAT]]* [[NP-полнота языка IND (максимальное независимое множество)]]* [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]]* [[NP-полнота языка CLIQUE]]* [[NP-полнота задач о гамильтоновом цикле и пути в графах]]* [[NP-полнота задачи о сумме подмножества]]* [[NP-полнота задачи о рюкзаке]]* [[NP-полнота задачи о раскраске графа]]* [[NP-полнота игры Тетрис]] === Сложность по памяти, классы PS, L, NL, coNL, EXP, NEXP ===*[[Класс PS. Связь класса PS с другими классами теории сложности]]*[[Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[PS-полнота задачи Generalized geography]]*[[Классы L, NL, coNL]]*[[Полнота относительно L-сведения. NL-полнота задачи о достижимости. P-полнота]]*[[Теорема Иммермана]]*[[Классы EXP и NEXP]] === Полиномиальная иерархия ===
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]
=== Классы задач подсчета ===
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
== Схемная сложность ==
*[[Схемная сложность и класс P/poly]]
*[[Теорема Карпа — Липтона]]
*[[Классы NC и AC]]
*[[Теорема о не принадлежности непринадлежности XOR классу AC⁰]] == Вероятностные сложностные классы ===== Основные классы ===
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы BPPweak RP и BPPstrongcoRP]]*[[Уменьшение ошибки в классе RPКласс ZPP]]*[[Классы BPP и PP]]*[[Соотношение вероятностных классов]]*[[Лемма Шварца-Зиппеля]]
*[[Теорема Лаутемана]]
*[[Теорема Валианта-Вазирани]]
=== Интерактивные протоколы ===
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Арифметизация булевых формул с кванторами]]
*[[Лемма Теорема о соотношении coNP и IP]]
*[[Теорема Шамира]]
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол ГолдвассераГолдвассер-Сипсера для оценки размера множества]] === Probabilistically checkable proofs ===*[[PCP-система]]*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]*[[PCP-теорема, альтернативное доказательство]]
----
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.
