Изменения

*# ''взяли'' [[Сложностные классы]](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. [[Примеры NP-полных языков]] ===# [[NP-полнота языка CNFSAT]] (1)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно# [[NP-полнота языка 3SAT]] (1)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно# [[NP-полнота языка IND (максимальное независимое множество)]] (3)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно## Добавить картинку графа-примера# [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]] (1)## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью## Оформить правильно# [[NP-полнота языка FACTOR]] (3)## Оформить правильно## Пояснить происходящее# [[NP-полнота языка CLIQUE]] (2)## Оформить правильно## Проинлайнить доказательство# '''fixed''' [[NP-полнота задач о гамильтоновом цикле и пути в графах]] (5)## Оформить правильно## Картинки сделать красивыми# ''fixed'' [[NP-полнота задачи о сумме подмножества]] (3)## Оформить правильно# [[NP-полнота задачи о рюкзаке]] (3)## Оформить правильно## Пояснить подробней# [[NP-полнота задачи о раскраске графа]] (2)## Оформить правильно

=== 34. Сложность по памяти, классы 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]]

=== 45. Полиномиальная иерархия ===*#[[Классы 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)## Сделать всё хорошо