NP-hardness

From Wikipedia, the free encyclopedia
Jump to: navigation, search

An NP-hard problem is a yes/no problem where finding a solution for it is at least as hard 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.

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 can use an algorithm check that it is true.

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 this, and this also cannot be checked.