NP-hardness

An NP-hard problem is a maths problem found in computer science. It is a yes/no problem where finding a solution for it is at least as hard as finding a solution for the hardest problem whose solution can quickly be checked as being true. Some NP-hard problems are ones where a working solution can be checked quickly (NP problems) and some are not. NP-hard problems that are also NP problems fit into a category called NP-complete.

Examples

An example of a problem that is at least as hard to solve as any other problem that we can quickly check solutions for, which is also quickly checkable (it is both NP-hard and NP):

A travelling salesman wants to visit 100 cities by driving, starting and ending his trip at home. He has a limited supply of gasoline, so he can only drive a total of 10,000 kilometers. He wants to know if he can visit all of the cities without running out of gasoline.

People don't know how to solve this problem faster than testing every possible answer, but if a solution is found that allows the salesman to do this, we can use an algorithm check that it is true. This problem is also known as Travelling salesman problem.

An example of a problem that is at least as hard to solve as any other problem that we can quickly check solutions for, but that can not be checked quickly (it is NP-hard, but it is not NP):

if someone starts a program that simply goes,

while(true){ continue; }

and never stops it, will it run forever?

There is no known way to find a solution to all problems of this kind, and this also cannot be checked.

NP-hardness Media

Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)