CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: NP Completeness

  1. Define P = PTIME = Polynomial Time = Fast!
  2. Define EXP = EXPTIME = Exponential Time = Slow!
  3. Define intractable = solveable in theory but too slow in practice
  4. Define subsetSum = given a list L, find a sublist M of values in L where sum(M) == 0.
  5. Show (by example) that subsetSum is in EXP = just try all 2**N sublists of L.
  6. Question: is subsetSum in P? Answer: nobody knows.
  7. Define NP = Non-Deterministic Polynomial Time = able to confirm answer in PTIME
  8. Show that subsetSum is in NP: easy to confirm if M is a sublist of L and sum(M) == 0.
  9. Define SAT (Boolean Satisfiability) = Given a circuit with N gates, is there some assignment of True/False values to its inputs that makes it output True? (Basically, in 112-speak, it's an ROC for boolean circuits).
  10. Show that SAT is in NP = Easy to just evaluate the circuit using given inputs.
  11. Discuss P-Time reductions between SAT and subsetSum = You can convert either problem into the other one quickly, so if you have a PTIME solution to one of them, you then have a PTIME solution for the other.
  12. So: subsetSum is in P if-and-only-if SAT is in P.
  13. So: subsetSum and SAT are NP-Complete
  14. Define NP-Complete: Problems in NP that have the additional property that if any one of them happens to be in P (fast!), then they all are in P!
  15. Show other problems that are NP-Complete See https://en.wikipedia.org/wiki/NP-completeness#NP-complete_problems
  16. Again: either all of these are in P or none of these are in P
  17. So the million-dollar question is if P =?= NP See here.
  18. Discuss economic significance of these problems (vast!)
  19. Discuss the Millenium Prize ($1M and fame and glory!) See here.
  20. Summarize: Does P = NP? We hope so, but who knows?