NP-complete

Adjective

NP-complete (not comparable)

1. That is both NP (solvable in polynomial time by a non-deterministic Turing machine) and NP-hard (such that any (other) NP problem can be reduced to it in polynomial time).
   • Informally, a problem is in the class NPC—and we refer to it as being NP-complete—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...2001, Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, Introduction To Algorithms, 2nd edition, The MIT Press, page 968
   • 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.2002, Thomas A. Garrity, All the Mathematics You Missed: But Need to Know for Graduate School, Cambridge University Press, page 317