NP-complete
Theoretical computer science
A problem in NP to which every other NP problem can be reduced in polynomial time, making it at least as hard as every problem in the class.
What is usually left out
Completeness is what makes the class tractable to reason about: a polynomial-time algorithm for any single NP-complete problem would give one for all of them, and thereby prove P = NP. Thousands of problems across scheduling, logic and graph theory are known to be NP-complete, which is why the question is not confined to theory.
Related terms
In the atlas
- P versus NP problem — Theoretical computer science, open