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

This article is provided by FOLDOC - Free Online Dictionary of Computing (
References in periodicals archive ?
Then, either ESO(Q) is regular, or ESO(Q) expresses some NP-complete language (Theorem 10.5).
(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. We also give a precise characterization of those ESO-prefix classes that are equivalent to MSO over strings, and of the ESO-prefix classes which are closed under complementation on strings.
We also know (e.g., by Fagin's Theorem) that some classes ESO(Q) allow us to express NP-complete languages. It is therefore important to know (i) which classes ESO(Q) can express NP-complete languages, and (ii) whether there are prefix classes ESO(Q) of intermediate complexity between regular and NP-complete classes.
The upper two regions contain all classes that express nonregular languages, and therefore, as we show, also NP-complete languages. The uppermost region contains those classes which capture NP, that is, express all languages in NP.
(i) ESO(I) expresses either only regular languages, or also some NP-complete languages; equivalently,