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