NP-complete


Also found in: Wikipedia.

NP-complete

(complexity)
(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.

http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/NP/.

References in periodicals archive ?
In this research, the routing problem of HMC is proven to be NP-complete and a heuristic algorithm is proposed to solve it.
In this article we prove that the problem of computing the minimum cardinality of an open 0-monopoly in a graph is NP-complete even restricted to bipartite or chordal graphs.
He identified a specific class of problem, termed NP-complete, whose defining trait, as he explained yesterday after being told of the award, is that "if you can show that a problem is NP-complete, then very likely you should give up trying to solve it.
As a main result, we show that deciding whether G admits a k-weak orientation is NP-complete for every k [greater than or equal to] 2.
Others are classified as NP-complete (NP stands for nondeterministic polynomial time) and are the hardest to crack.
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.
It is well known that determining the treewidth of a graph poses an NP-complete problem, but its restriction to graphs with bounded treewidth is decidable in polynomial time [1].
Much of the work on DNA computing has continued to focus on solving NP-complete and other hard computational problems.
DNA computing was introduced by Adleman in 1994 who has explained how to use biological tools to solve NP-Complete problems [1, 8].
Complexity of this pencil puzzle is said to belong to a set of NP-complete class of problems (Ruepp & Holzer, 2010).
However, essentially, all such problems are NP-complete as this is true even with respect to Plurality-WEIGHTED-$BRIBERY.