Изменения

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

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

=== Полиномиальная иерархия 3. [[Примеры NP-полных языков]] ===*# [[NP-полнота языка CNFSAT]] (1)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно# [[Классы PHNP-полнота языка 3SAT]] (1)## Выпилить из большого конспекта, Σ а в нём сделать ссылку как на основную статью## Оформить правильно# [[NP-полнота языка IND (максимальное независимое множество)]] (3)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно## Добавить картинку графа-примера# [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]] (1)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно# [[NP-полнота языка FACTOR]] (3)## Оформить правильно## Пояснить происходящее# [[NP-полнота языка CLIQUE]] (2)## Оформить правильно## Проинлайнить доказательство# '''fixed''' [[NP-полнота задач о гамильтоновом цикле и Πпути в графах]] (5)## Оформить правильно## Картинки сделать красивыми# ''fixed'' [[NP-полнота задачи о сумме подмножества]](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)## Отформатировать по правилам## Привести примеры, где может быть актуально решать такую задачу#[[Классы L, NL, coNL]] (3)## Отформатировать по правилам## Добавить больше неформальных пояснений к классам## Добавить ещё несколько утверждений про связи классов L с другими## Помёрджить с этим конспектом и другими из треша: [[NL-полнота]]#[[Полнота относительно L-сведения. NL-полнота. P/poly-полнота]](2)## Отформатировать по правилам*#[[Теорема Карпа — ЛиптонаИммермана]](2)## Отформатировать по правилам*# [[Классы NC EXP и ACNEXP]](4)*## Смёрджить два конспекта и отформатировать по правилам: [[Классы EXP, NEXP. Полнота языков EXP и NEXP]], [[Теорема о непринадлежности XOR классу AC⁰связи вопросов EXP=NEXP и P=NP]]

== Вероятностные сложностные классы = 5. Полиномиальная иерархия ===*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]*#[[Классы RP PH, Σ и coRPΠ]](3)*[[Класс ZPP]]## Отформатировать по правилам*## Доказать простенькие отношений отсюда: [[Классы BPP Sigma i и PPPi i]]*, [[Соотношение вероятностных классовПолиномиальная иерархия]]*#[[Теорема ЛаутеманаТеоремы о коллапсе полиномиальной иерархии]](2)## Отформатировать по правилам

=== Интерактивные протоколы =2. Схемная сложность ==*#[[Интерактивные протоколы. Класс IP. Класс AMСхемная сложность и класс P/poly]](1)*[[Арифметизация булевых формул с кванторами]]## Отформатировать по правилам*#[[Теорема о соотношении coNP и IPКарпа — Липтона]](2)## Отформатировать по правилам*## Помёрджить с [[Теорема ШамираКарпа-Липтона]](0.5)*#[[Семейство универсальных попарно независимых хеш-функцийКлассы NC и AC]]*## Добавить Источники информации и См. также#[[Протокол Голдвассер-Сипсера для оценки размера множестваТеорема о непринадлежности XOR классу AC⁰]](2)## Оформить по правилам

==3. Вероятностные сложностные классы = ==== 1. Основные классы ===#[[Вероятностные вычисления. Вероятностная машина Тьюринга]] (2)## Отформатировать по правилам## Помёрджить с [[Вероятностная машина Тьюринга]]#[[Классы RP и coRP]] (3)## Отформатировать по правилам## Помёрджить с [[Сложностные классы RP и coRP]] и [[Уменьшение ошибки в классе RP, сильное и слабое определение]]#[[Класс ZPP]] (2)## Отформатировать по правилам## Помёрджить с [[Сложностный класс ZPP]]#[[Классы BPP и PP]] (3)## Отформатировать по правилам## Помёрджить с [[Сложностный класс PP]] и [[Сложностный класс BPP]]#[[Соотношение вероятностных классов]] (2)## Отформатировать по правилам## Добавить сюда [[Теорема о включении 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)## Сделать всё хорошо