NP-complete

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

An NP problem is a yes/no problem whose answer depends on the numbers input (a decision problem) where every "yes" answer could be verified in a feasible amount of time (polynomial time) by a computer that could manipulate an unlimited amount of data (deterministic turing machine).

An NP-complete problem is an NP problem where there are no known series of steps (algorithms) that could solve the problem in a feasible amount of time.

The Travelling salesman problem is an NP-Complete problem.

NP-complete decision problems are the hardest problems in NP. If there is a polynomial-time algorithm for even one of them, then there is a polynomial-time algorithm for all the problems in NP. Because of this, and because dedicated research has failed to find a polynomial algorithm for any NP-complete problem, once a problem has been proven to be NP-complete it is widely regarded that a polynomial algorithm for this problem is unlikely to exist.

The unsolved problem P = NP asks whether polynomial time algorithms actually exist for NP-complete, and by corollary, all NP problems. It is widely believed that this is not the case.