Изменения

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

*# [[Класс 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: [[Редкие языки]]

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

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

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

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

*# [[PCP-система]](3)*## Отформатировать по правилам# [[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]](4)*## Отформатировать по правилам## Написать понятней## Пояснить, что даёт эта эквивалентность# '''!!!''' [[PCP-теорема]](10)## Сделать всё хорошо