Изменения

Некоторые задачи из <tex>\mathrm{P}</tex> очень похожи на задачи из <tex>\mathrm{NP}</tex>. В каждой из приведенных ниже пар задач первая разрешима за полиномиальное время, а вторая является при этом различие между задачами кажется совершенно незначительным:{| class="wikitable"|-!Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полной. При этом различие между задачами кажется совершенно незначительным.полная|-*Поиск |[[Обход_в_ширину|Поиск самых короткихпростых путей]] и ||[//en.wikipedia.org/wiki/Longest_path_problem Поиск самых длинных простых путей;]|-*|[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеровцикл]] и ||[[Гамильтоновы_графы|гамильтоновГамильтонов цикл]] циклы;*|-|[http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf 2-CNF и выполнимость]||[[Примеры NP-полных языков#NP-полнота 3-SAT|3-CNF выполнимость.]]|}