NP-твердая задача - это задача "да/нет", где найти решение по крайней мере так же сложно, как найти решение для самой сложной задачи, решение которой можно быстро проверить как истинное. Некоторые NP-жесткие задачи - это задачи, в которых работающее решение может быть проверено быстро (NP задачи), а некоторые нет. NP-задачи, которые также являются NP-задачами, попадают в категорию, называемую NP-завершенными.

Пример проблемы, которая хотя бы так же сложна в решении, как и любая другая проблема, для которой можно быстро проверить решения, что также быстро проверяется (это и NP-твердый, и NP-твердый):

Путешествующий продавец хочет посетить 100 городов за рулем, начав и закончив свою поездку дома. У него ограниченный запас бензина, поэтому он может проехать всего 10 000 километров. Он хочет знать, может ли он посетить все города, в которых не заканчивается бензин.

Люди не знают, как решить эту проблему быстрее, чем проверять каждый возможный ответ, но если найдено решение, позволяющее это сделать продавцу, то можно воспользоваться алгоритмом проверки, что это правда. Эта проблема также известна как проблема коммивояжера путешествий.

Пример проблемы, которая хотя бы так же сложна в решении, как и любая другая проблема, для которой можно быстро проверить решения, но которая не может быть быстро проверена (она NP-твердая, но это не NP):

если кто-то запускает программу, которая просто идет,

в то время как(правда){ продолжай; }

и никогда не остановит его, будет ли он работать вечно?

Нет известного способа найти решение всех проблем подобного рода, и это тоже нельзя проверить.