Изменения
→Связь P и NP
*[http://arxiv.org/abs/1011.3944 «решение» 3SAT за полиномиальное время];
*[http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf задача о коммивояжере].
Некоторые задачи из <tex>\mathrm{P}</tex> очень похожи на задачи из <tex>\mathrm{NP}</tex>. В каждой из приведенных ниже задач пар задач одна разрешима за полиномиальное время, а другая является <tex>\mathrm{NP}</tex>-полной. При этом различие между задачами кажется совершенно незначительным.
*Поиск самых коротких и самых длинных простых путей;
*[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров]] и [[Гамильтоновы_графы|гамильтонов]] циклы;
*2-CNF и 3-CNF выполнимость.
== См. также ==
