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