(redirected from NP complete)


(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 ?
We first show that such a problem is NP complete by proving that it is a special case of a well known multi-constrained 0-1 knapsack problem.
It is necessary for DNA computation to expand its algorithmic techniques, incorporate approximative and probabilistic algorithms and heuristics, so that the solution of large instances of NP complete problems will be possible.
This system can be used to solve a variety of NP complete problems.
In section 4, the paper presents the biological bases for Innate Immune then introduces the concept of adding innate immunity to membrane computing and demonstrates how it can be used to attack NP complete problems in linear time less than time taken by a P system without protection of immunity.
It has been proven that Recognizer P systems can solve NP complete problems in polynomial time or less [13], [14].
[6] study this problem as a geometric embedding problem and prove it is NP Complete by reduction from the 3-satisfiability problem (3SAT) (1).
This condition is referred to as NP complete (non-deterministic polynomial complete) and is a measure of the problems complexity.
The NP completes the discharge summary for all patients on the day of discharge to enhance timely insurance reimbursement, and to communicate about follow-up with the primary care providers.
In clinics, the NP completes complex health assessment, develops patient care plans and ensures the provision of care, all in an effort to manage early diabetic complications and delay the progression to end stage renal disease.