CMU 15112: Fundamentals of Programming and Computer Science
Class Notes: NP Completeness

Define P = PTIME = Polynomial Time = Fast!

Define EXP = EXPTIME = Exponential Time = Slow!

Define intractable = solveable in theory but too slow in practice

Define subsetSum = given a list L, find a sublist M of values in L where sum(M) == 0.

Show (by example) that subsetSum is in EXP = just try all 2**N sublists of L.

Question: is subsetSum in P? Answer: nobody knows.

Define NP = NonDeterministic Polynomial Time = able to confirm answer in PTIME

Show that subsetSum is in NP: easy to confirm if M is a sublist of L and sum(M) == 0.

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 112speak, it's an ROC for boolean circuits).

Show that SAT is in NP = Easy to just evaluate the circuit using given inputs.

Discuss PTime 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.

So: subsetSum is in P ifandonlyif SAT is in P.

So: subsetSum and SAT are NPComplete

Define NPComplete: 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!

Show other problems that are NPComplete
See https://en.wikipedia.org/wiki/NPcompleteness#NPcomplete_problems

Again: either all of these are in P or none of these are in P

So the milliondollar question is if P =?= NP
See here.

Discuss economic significance of these problems (vast!)

Discuss the Millenium Prize ($1M and fame and glory!)
See here.

Summarize: Does P = NP? We hope so, but who knows?