NP-completeness (under construction)
Summary
A problem L is NP-complete if it is in NP and every other problem in NP can be reduced to L. NP-complete problems are therefore the "hardest" problems in NP: if any NP-complete problem has a polynomial time solution, then P = NP. Many widely studied problems are NP-complete, and practically speaking, one might as well give up looking for polynomial time algorithms for such problems.
Notes
This concept is still under construction.
Context
This concept has the prerequisites:
- NP complexity class (NP-complete problems are the hardest problems in NP.)
- propositional satisfiability (SAT is the canonical NP-complete problem.)
- nondeterministic Turing machines (Cook's Theorem is proved by defining nondeterministic Turing machines through SAT clauses.)
Goals
- Know what is meant by a polynomial time reduction
- Know the distinction between the terms "in NP," "NP-hard," and "NP-complete"
- Know the statement of Cook's Theorem (that SAT is NP-complete)
- Prove Cook's theorem
- Be able to prove problems NP-complete
See also
-No Additional Notes-