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

This article is provided by FOLDOC - Free Online Dictionary of Computing (
References in periodicals archive ?
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].
Until now, many kinds of P systems can solve some NP-complete problems, such as SAT [4-10], 3coloring problem [11], and Hamiltonian cycle problem [12].
Parameterized Complexity offers various notions and useful tools that has became standard in modern analysis of NP-complete problems. The problems are studied with respect to numerical attributes (parameters) of instances.
In this paper, we applied sticker model for solving the knapsack problem which is one of the NP-complete problems.
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.
[I.sub.1] includes those problems, for which the existing algorithm is a polynomial one, and [I.sub.2] (which includes NP-complete problems), those for which no polynomial time algorithms are known (Koblitz, 1998).
The answer is that it is generally suspected by complexity theorists to be impossible for a quantum computer to solve the SUBSET-SUM problem (and all other problems which share a characteristic with the SUBSET-SUM problem in that they belong to a subclass of NP problems known as NP-complete problems [5]) in polynomial-time.
BAKER, Approximation algorithms for np-complete problems on planar graphs, in Proc.