Изменения

# '''взялиfixed''' [[Классы NP и Σ₁]] (7)

# ''fixed'' [[NP-полнота BH1N]] (1)

# ''взяли'' [[Теорема Кука]] (2)

# [[Теорема Бейкера — Гилла — Соловэя]] (34)

# ''fixed'' [[Теорема Махэни]] (34)

# '''!!!fixed''' [[NP-полнота задач о гамильтоновом цикле и пути в графах]] (75)

# ''fixed'' [[NP-полнота задачи о сумме подмножества]] (3)

=== 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]]

*#[[Классы 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)## Сделать всё хорошо