NP-hardness and NP-completeness
NP-completeness combines verification and reduction hardness.
Key knowledge
A decision problem B is NP-hard when every problem in NP has a polynomial-time reduction to B. B is NP-complete when it is also in NP. A polynomial algorithm for any NP-complete problem would give polynomial algorithms for all NP problems.
Conditions and scope
- Here reductions are polynomial-time many-one transformations preserving yes/no answers.
- NP-hard problems need not themselves be in NP; hardness is a worst-case classification.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Physical pages 2–3: polynomial decision/verification, certificate conditions, reductions and NP-completeness.
2026-10-10 · Lecture 19 reduction definitions and consequences.
Entry details
Permanent link to this entry ↗- Record identity
- info-np-completeness
- Revision
- university-reference.1
- Structured reference record
- University reference