Изменения

== 1. Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==*=== 1. Базовые определения ===# ''взяли'' [[Сложностные классы]](3)*## Убрать пункт История## Прафильно раставить тех## Сделать отсылку к теорию вычислимости## Сформулировать определения в терминах МТ (смотри трешовую версию)## Категории## См. также, Источники информации## Возможно добавить ещё чуть-чуть информации с википедии или откуда-нибудь## Интервики# [[Вычисления с оракулом]](1)## Добавить различные определения сведения, в том числе из трешовой версии## Отформатировать по правилам

=== 2. Классы P и NP, NP-полнота ===*# [[Класс P]](3)## Отформатировать по правилам## Добавить про тильду*# ''взяли'' [[Недетерминированные вычисления]](2)## Отформатировать по правилам## Какую-нибудь разумную структура конспекта создать## Добавить примеров*# '''fixed''' [[Классы NP и Σ₁]](7)## Отформатировать по правилам## Доказать для некоторых языков из примеров, что они в NP*## Ещё простых примеров с доказательством## Добавить определение coNP, примеры языков по возможности с доказательствами# [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]](1.5-2)## Отформатировать по правилам*## Возможно добавить ещё более простой пример# ''fixed'' [[NP-полнота BH1N]](1)## Отформатировать по правилам*# ''взяли'' [[Теорема Кука]](2)*[[Примеры NP-полных языков]]## Отформатировать по правилам## Сделать табличку красивой*# [[Теоремы о временной и емкостной иерархиях]](1)## Отформатировать по правилам*# [[Теорема Бейкера — Гилла — Соловэя]](4)*## Отформатировать по правилам## Пояснить подробней все переходы## Пояснить подробней последнюю теорему, дать ссылки примечаниями# [[Теорема Ладнера]](2)*## Отформатировать по правилам# [[Теорема Левина]](2)## Отформатировать по правилам## Пояснить неформальный смысл теоремы## Возможно подробней описать*# [[Теорема Бермана — Форчуна]](2)## Отформатировать по правилам## Добавить структуру конспекту*# ''fixed'' [[Теорема Махэни]] (4)## Отформатировать по правилам## Пояснить обозначения в начале## Добавить, что такое SPARSE: [[Редкие языки]]

=== Сложность по памяти, классы PS, L, NL, coNL 3. [[Примеры NP-полных языков]] ===*# [[Класс PS. Связь класса PS с другими классами теории сложностиNP-полнота языка CNFSAT]](1)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно*# [[Теорема Сэвича. Совпадение классов NPS и PSNP-полнота языка 3SAT]](1)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью*## Оформить правильно# [[PSNP-полнота языка верных булевых формул с кванторами IND (TQBFмаксимальное независимое множество)]](3)*## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно## Добавить картинку графа-примера# [[Классы LNP-полнота языка VCOVER (минимальное вершинное покрытие)]] (1)## Выпилить из большого конспекта, NL, coNLа в нём сделать ссылку как на основную статью## Оформить правильно# [[NP-полнота языка FACTOR]] (3)## Оформить правильно## Пояснить происходящее# [[NP-полнота языка CLIQUE]](2)## Оформить правильно## Проинлайнить доказательство*# '''fixed''' [[Полнота относительно LNP-сведения. NLполнота задач о гамильтоновом цикле и пути в графах]] (5)## Оформить правильно## Картинки сделать красивыми# ''fixed'' [[NP-полнота. Pзадачи о сумме подмножества]] (3)## Оформить правильно# [[NP-полнотазадачи о рюкзаке]](3)## Оформить правильно## Пояснить подробней*# [[Теорема ИммерманаNP-полнота задачи о раскраске графа]](2)## Оформить правильно

=== Полиномиальная иерархия 4. Сложность по памяти, классы PS, L, NL, coNL, EXP, NEXP ===*#[[Класс PS. Связь класса PS с другими классами теории сложности]] (1)## Отформатировать по правилам## Как-то помёрджить с [[Класс PS]]#[[Теорема Сэвича. Совпадение классов NPS и PS]] (1)## Отформатировать по правилам #[[PS-полнота языка верных булевых формул с кванторами (TQBF)]] (1)## Отформатировать по правилам # [[PS-полнота задачи Generalized geography]] (4)## Отформатировать по правилам## Привести примеры, где может быть актуально решать такую задачу#[[Классы PHL, NL, Σ coNL]] (3)## Отформатировать по правилам## Добавить больше неформальных пояснений к классам## Добавить ещё несколько утверждений про связи классов L с другими## Помёрджить с этим конспектом и Πдругими из треша: [[NL-полнота]]#[[Полнота относительно L-сведения. NL-полнота. P-полнота]] (2)## Отформатировать по правилам#[[Теорема Иммермана]](2)*## Отформатировать по правилам# [[Теоремы Классы EXP и NEXP]] (4)## Смёрджить два конспекта и отформатировать по правилам: [[Классы EXP, NEXP. Полнота языков EXP и NEXP]], [[Теорема о коллапсе полиномиальной иерархиисвязи вопросов EXP=NEXP и P=NP]]

== Схемная сложность = 5. Полиномиальная иерархия ===*#[[Схемная сложность Классы PH, Σ и класс P/polyΠ]](3)*## Отформатировать по правилам## Доказать простенькие отношений отсюда: [[Теорема Карпа — ЛиптонаКлассы Sigma i и Pi i]]*, [[Классы NC и ACПолиномиальная иерархия]]*#[[Теорема Теоремы о непринадлежности XOR классу AC⁰коллапсе полиномиальной иерархии]](2)## Отформатировать по правилам

== Вероятностные сложностные классы 2. Схемная сложность ==*#[[Вероятностные вычисления. Вероятностная машина ТьюрингаСхемная сложность и класс P/poly]](1)*## Отформатировать по правилам#[[Классы RP и coRPТеорема Карпа — Липтона]](2)## Отформатировать по правилам*## Помёрджить с [[Класс ZPPТеорема Карпа-Липтона]](0.5)*#[[Классы BPP NC и PPAC]]*[[Соотношение вероятностных классов]]## Добавить Источники информации и См. также*#[[Теорема Лаутеманао непринадлежности XOR классу AC⁰]](2)## Оформить по правилам

== 3. Вероятностные сложностные классы ===== Интерактивные протоколы 1. Основные классы ===*#[[Интерактивные протоколыВероятностные вычисления. Вероятностная машина Тьюринга]] (2)## Отформатировать по правилам## Помёрджить с [[Вероятностная машина Тьюринга]]#[[Классы RP и coRP]] (3)## Отформатировать по правилам## Помёрджить с [[Сложностные классы RP и coRP]] и [[Уменьшение ошибки в классе RP, сильное и слабое определение]]#[[Класс IP. Класс AMZPP]] (2)## Отформатировать по правилам## Помёрджить с [[Сложностный класс ZPP]]*#[[Арифметизация булевых формул Классы BPP и PP]] (3)## Отформатировать по правилам## Помёрджить с кванторами[[Сложностный класс PP]]и [[Сложностный класс BPP]]#[[Соотношение вероятностных классов]] (2)## Отформатировать по правилам*## Добавить сюда [[Теорема о соотношении coNP и IPвключении BPP в P/poly]]*#[[Теорема ШамираЛемма Шварца-Зиппеля]](3)*## Отформатировать по правилам#[[Семейство универсальных попарно независимых хеш-функцийТеорема Лаутемана]](1)## Отформатировать по правилам *#[[Протокол ГолдвассерТеорема Валианта-Сипсера для оценки размера множестваВазирани]](3)## Отформатировать по правилам

=== 2. Интерактивные протоколы ===# ''fixed'' [[Интерактивные протоколы. Класс IP. Класс AM]] (4)## Отформатировать по правилам## Увеличить картинку## Написать больше неформальных пояснений## +1 за более красивую векторную картинку# [[Арифметизация булевых формул с кванторами]] (4)## Отформатировать по правилам## Добавить структуру конспекту## Написать непонятные места понятней# ''fixed'' [[Теорема о соотношении coNP и IP]] (4)## Отформатировать по правилам## Написать непонятные места понятней# [[Теорема Шамира]] (3)## Отформатировать по правилам# '''взяли''' [[Семейство универсальных попарно независимых хеш-функций]] (5)## Отформатировать по правилам## Интервики на конспекты хеширования, там уже что-то есть про универсальное семейство# '''!!!''' [[Протокол Голдвассер-Сипсера для оценки размера множества]] (7)## Написать понятно## Отформатировать по правилам## Переименовать конспект## Добавить [[Теорема Голдвассера, Сипсера | теорему]] (+3 за правильное доказательство) === 3. Probabilistically checkable proofs ===*# [[PCP-система]](3)## Отформатировать по правилам*# [[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]](4)## Отформатировать по правилам## Написать понятней## Пояснить, что даёт эта эквивалентность*# '''!!!''' [[PCP-теорема]](10)## Сделать всё хорошо