Изменения

Перейти к: навигация, поиск

Классы NP, coNP, Σ₁, Π₁

11 байт убрано, 18:01, 4 июня 2012
Нет описания правки
Тут должен быть заголовок.
== NP и Σ₁ Определение ==
{{Определение
|definition=<tex>\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))</tex>.
*Поиск [[Обход_в_ширину|самых коротких]] и самых длинных простых путей;
*[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров]] и [[Гамильтоновы_графы|гамильтонов]] циклы;
*<tex>2-CNF</tex> и <tex>3-CNF</tex> выполнимость.
== См. также ==

Навигация