Изменения
→Связь P и NP
Некоторые задачи из <tex>\mathrm{P}</tex> очень похожи на задачи из <tex>\mathrm{NP}</tex>. В каждой из приведенных ниже задач пар задач одна разрешима за полиномиальное время, а другая является <tex>\mathrm{NP}</tex>-полной. При этом различие между задачами кажется совершенно незначительным.
*Поиск [[Обход_в_ширину|самых коротких ]] и самых длинных простых путей;
*[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров]] и [[Гамильтоновы_графы|гамильтонов]] циклы;
*<tex>2-CNF </tex> и <tex>3-CNF </tex> выполнимость.
== См. также ==
