- Optional presentations
- Colloquium
- “History of Calculus”
- Profs. Jeff Johannes and Gary Towsley
- Wednesday, November 18, 2:30 - 3:45
- Newton 204
- Likely to be crowded, get there early if you can
- Usual extra credit offer
- Problem set - P closed under complement means what?
- Given L in P
- Is L′ also in P?
- L′ = Σ* - L
- Summary of section 34.3 “NP-completeness” and “Circuit
satisfiability”
- Define NP complete
- L is NP complete if
- L in NP
- And for all K in NP, K polynomial-time reducible to L
- L is NP complete if
- Circuit satisfiability
- Circuit with boolean components (and, or, not) and one boolean output
- Circuit satisfiable if truth values can be assigned to inputs to make output true
- CIRCUIT-SAT = set of satisfiable circuits
- Truth tables
- Proof that CIRCUIT-SAT is NP-complete
- In NP: verifier takes circuit & assignment of values to wires, verifier can run in linear time
- Any problem in NP reduces to CIRCUIT-SAT
- How computers store configurations in memory
- Instructions map configurations to others
- Outline of proof
- Simulating computer fetch-execute cycle
- A computer’s electronics executes roughly this algorithm:
loop forever read instruction from memory execute instruction (combinational) write result back to memory increment program counter
- A computer’s electronics executes roughly this algorithm:
- The body of this loop can be implemented by a combinational circuit
- Cascade many, but only polynomially many, copies of this, one copy per
step in the verification algorithm
- Now that we can reduce any problem in NP to CIRCUIT-SAT, we can
prove other problems NP complete by reducing CIRCUIT-SAT to them
- Such a reduction provides a 2-step reduction of any problem in
NP to the new one
- Such a reduction provides a 2-step reduction of any problem in
NP to the new one
- Define NP complete
- Original Cook-Levin proof is a little different from this
- Constructed a boolean formula (instance of SAT) from a Turing machine
- Proving NP completeness
- Read section 34.4