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/.

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
Unfortunately the problem becomes NP-complete already for k = 3 [1].
In this research, the routing problem of HMC is proven to be NP-complete and a heuristic algorithm is proposed to solve it.
The (decision variant of the) MAX CUT is one of the Karp s original NP-complete problems [2] and has long been known to be NP-complete even if the problem is unweighted, that is, if [w.sub.ij] = 1 for all (i,j) [member of] E [3].
As a well-known NP-complete problem, SAT problem has been widely used in artificial intelligence and electronic design automation.
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.
This can be done since 3-SAT is NP-complete. If there is an algorithm that can solve 3-SAT in polynomial-time, then it would also be able to solve SUBSET-SUM in polynomial-time, contradicting Feinstein's lower-bound claim of [THETA]([square root of [2.sup.n]]).
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.
If a certain group of solution to this problem was proved NPcomplete, then the whole group of solutions to this problem must be NP-complete.