(redirected from NP-complete language)


(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 ?
Then, either ESO(Q) is regular, or ESO(Q) expresses some NP-complete language (Theorem 10.
ii) the satisfiability problem for FO(I) is undecidable and ESO(I) defines some NP-complete language.
We further prove the following dichotomy theorem: An ESO prefix-class either expresses only regular languages (and is thus in MSO), or it expresses some NP-complete languages.
by Fagin's Theorem) that some classes ESO(Q) allow us to express NP-complete languages.
The upper two regions contain all classes that express nonregular languages, and therefore, as we show, also NP-complete languages.
2 do not only express nonregular languages, they even express NP-complete languages.