NP-complete adjective1 •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).A problem Π is said to be NP-complete if each problem in NP is reducible to Π. Hence (4.13) if some NP-complete problem belongs to P, then P=NP. — 2003
