Изменения

'''Примечание:'''определение <tex>\mathrm{\Sigma_1}</tex> часто называют также «определением NP на языке сертификатов».

{{Теорема

|statement=

}}

* Язык раскрасок графа в <tex>k</tex> цветов;

* Язык гамильтоновых графов;

Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. [[Теорема_Ладнера|О существовании не полного <tex>\mathrm{NP}</tex> языка]].

Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]]; различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:

*[http://arxiv.org/abs/1011.3944 «решение» 3SAT за полиномиальное время];