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