Разница между NP-трудными и NP-полными задачами заключается в том, что первые не обязательно принадлежат классу NP, а вторые одновременно являются NP-трудными и относятся к классу NP. 12

NP-трудные задачи (NP-hard) — это задачи, которые не менее сложны, чем самые сложные задачи в классе NP, но не обязательно принадлежат самому классу NP. 12 Такие задачи могут быть даже неразрешимы. 2 Примеры: задача оптимизации, задача остановки, головоломка о перемещении пианино. 1

NP-полные задачи (NP-complete) — это самые сложные задачи в классе NP. 1 Каждая NP-полная задача должна быть в NP и сводиться к любой другой задаче из NP-полных. 2 Если для одной NP-полной задачи будет найден полиномиальный алгоритм, то все задачи в классе NP также смогут быть решены за полиномиальное время. 1 Примеры: задача коммивояжёра, задача о раскраске графа, задача о выполнимости булевых формул (SAT). 1