NP-Complete
← Back to Complexity Classes
The hardest problems in NP: every problem in NP can be reduced to an NP-Complete problem in polynomial time. If any NP-Complete problem has a polynomial-time solution, then P = NP.
Key Properties
Related
- NP (NP-Complete problems are in NP)
- NP-Hard (at least as hard)
- Polynomial-Time Reductions (how NP-completeness is proved)