Jump to content

NP-hardness

From Simple English Wikipedia, the free encyclopedia

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

[change | change source]

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.