130
правок
Изменения
→Связь P и NP: Заменил внешнюю ссылку на примечание
!Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полная
|-
|[[Обход_в_ширину|Поиск самых коротких простых путей]]||Поиск самых длинных простых путей<ref>[//en.wikipedia.org/wiki/Longest_path_problem Поиск самых длинных простых путейLongest path problem - Wikipedia]</ref>
|-
|[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл]]||[[Гамильтоновы_графы|Гамильтонов цикл]]
|[[2SAT|2-CNF выполнимость]]||[[Примеры NP-полных языков#NP-полнота 3-SAT|3-CNF выполнимость]]
|}
== См. также ==
