(redirected from NP-complete problems)


(NPC, Nondeterministic Polynomial time complete) A set or property of computational decision problems which is a subset of NP (i.e. can be solved by a nondeterministic Turing Machine in polynomial time), with the additional property that it is also NP-hard. Thus a solution for one NP-complete problem would solve all problems in NP. Many (but not all) naturally arising problems in class NP are in fact NP-complete.

There is always a polynomial-time algorithm for transforming an instance of any NP-complete problem into an instance of any other NP-complete problem. So if you could solve one you could solve any other by transforming it to the solved one.

The first problem ever shown to be NP-complete was the satisfiability problem. Another example is Hamilton's problem.

See also computational complexity, halting problem, Co-NP, NP-hard.

References in periodicals archive ?
Parameterized Complexity offers various notions and useful tools that has became standard in modern analysis of NP-complete problems.
On the one hand, we plan to use complexity lower bound techniques as inspiration to design new and improved algorithms for Satisfiability and other NP-complete problems, as well as to analyze existing algorithms better.
DNA computing was introduced by Adleman in 1994 who has explained how to use biological tools to solve NP-Complete problems [1, 8].
The class of NP-Complete problems is a subset of NP problems.
The SAT problem is central in the class of NP-Complete problems.
Also NP-complete problems, their role in our daily life, and the crucial role in technology in their study, will be discussed.
BAKER, Approximation algorithms for np-complete problems on planar graphs, in Proc.
We assume here a familiarity with the rudiments of the theory of computational complexity and NP-complete problems as given by Garey & Johnson (1979).
If a polynomial time algorithm capable of solving any one of the problems known to be NP-complete could be found, it would follow (because of the nature of the equivalence class formed by the NP-complete problems) that all the NP-complete problems could also be solved in polynomial time.
108) The oldest of these is called the class of NP-complete problems.
It is one of the most famous NP-Complete problems, and even approximating the chromatic number within an acceptable ratio is NP-hard [7].