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:

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-