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 the shortest way to visit all 100 cities, so he can visit them all 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 to quickly check that it is correct. This problem is also known as the 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 cannot 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. This is also known as the Halting problem.
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)
