NPcomplete
Jump to navigation
Jump to search
See also: NPcomplète
English[edit]
Adjective[edit]
NPcomplete (not comparable)
 (computing theory, of a decision problem) That is both NP (solvable in polynomial time by a nondeterministic Turing machine) and NPhard (such that any (other) NP problem can be reduced to it in polynomial time).
 2001, Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, Introduction To Algorithms, 2nd edition, The MIT Press, page 968:
 Informally, a problem is in the class NPC—and we refer to it as being NPcomplete—if it is in NP and is as "hard" as any problem in NP. We shall formally define what it means to be as hard as any problem in NP later in this chapter. In the meantime, we will state without proof that if any NPcomplete problem can be solved in polynomial time, then every problem in NP has a polynomialtime algorithm. Most theoretical computer scientists believe that the NPcomplete problems are intractable, since given the wide range of NPcomplete problems that have been studied to date—without anyone having discovered a polynomialtime solution to any of them—it would be truly astounding if all of them could be solved in polynomial time. Yet, given the effort devoted thus far to proving NPcomplete problems intractable—without a conclusive outcome—we cannot rule out the possibility that the NPcomplete problems are in fact solvable in polynomial time.
 2002, Thomas A. Garrity, All the Mathematics You Missed: But Need to Know for Graduate School, Cambridge University Press, page 317:
 Every area of math seems to have its own NP complete problems. For example, the question of whether or not a graph contains a Hamiltonian circuit is a quintessential NP complete problem and, since it can be explained with little higher level math, is a popular choice in expository works.
 2003, A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Volume A, Springer, page 43:
 A problem Π is said to be NPcomplete if each problem in NP is reducible to Π. Hence
(4.13) if some NPcomplete problem belongs to P, then P=NP.
Related terms[edit]
 NP
 NPC / NPC (the set of NPcomplete problems)
 NPcompleteness
 NPhard
 NPeasy
 NPequivalent
Translations[edit]
both NP and NPhard

Further reading[edit]
 P versus NP problem on Wikipedia.Wikipedia