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?