P vs NP
Summer 2009: M,Th 1-2:30pm, STARTING MAY 11
...to make progress on hard problems one needs to have a certain world view, keep positive, and believe that a solution is possible. We must not let impossibility theorems scare us into not thinking about problems. We can let them guide us, we can let them show us what we cannot do, and what we can do. But we must move forward. -- Dick Lipton
Location: Graphics Annex.
- Suresh Venkatasubramanian, Assistant Professor, School of Computing
- Parasaran Raman, PhD Student, School of Computing
- John Moeller, PhD Student, School of Computing
- Raj Varma Kommaraju, MS Student, School of Computing
- Jagadeesh Jagarlamudi, PhD Student, School of Computing
- Scott Alfeld, MS Student, School of Computing
- Avishek Saha, PhD Student, School of Computing
- Seth Juarez, PhD Student, School of Computing
|Basics and Diagonalization|
|May 11||Review of basic TM definitions, recursiveness and r.e problems. Diagonalization (real numbers, halting problem). Dr. Seuss proof of the halting problem||Suresh|
|May 14||Time and space hierarchy theorems, particularly for deterministic/nondeterministic time, and deterministic space.||Avishek, Parasaran|
|May 18||The Nondeterministic time hierarchy and Ladner's theorem (discuss here)||Carlos, John|
|May 21||Oracle Machines and the BGS result, and an alternate proof from Jin-yi Cai||Jags, Chris|
|May 28||Circuits and Advice: Nonuniform complexity. First three sections of Chapter 6 (and some questions to ponder)||Raj, Suresh|
|Jun 1||More Circuits: AC, NC, and some lower bounds. Chapter 6.3, 6.5 and Section 2.3 of the survey|
|Jun 3||Parity and the switching lemma (Chapter 13.1)|
| ||Circuits with counters (Chapter 13.2)|
|Jun 25||Monotone circuits (Chapter 13.3) and notes of V. Aravind|
|Jul 13||Pseudorandom generators|
|Jul 16||Natural Proofs|
Attempt 1: Diagonalization
How diagonalization works to prove lower bounds, and what the Baker-Gill-Solovay oracle result implies for this approach.
- Lance's paper on diagonalization
Attempt 2: Circuit lower bounds
Lower bounds for circuit problems, getting closer and closer, and then Razborov-Rudich
Monotonic Lower bounds for Circuits
Lemma: CLIQUE(n,k) needs exponential number of indicators functions for sufficient approximation.
On the other hand, Indicator functions can be used to well approximate monotonic functions. If clique can be approximated by monotonic function then clique can be approximated using small number of clique indicator functions, which contradicts our first lemma. Thus clique can't be approximated using monotoic function (hence by a monotonic circuit).
Lower bounds for SAT
A complexity proof that's neither relativistic nor natural.
Attempt 3: Geometry, and P vs NC
Mulmuley's geometric attack
Attempt 4: The Algebraization problem
Aaronson+Wigderson, and related work.
Attempt 5: NP vs co-NP
Attempt 6: P vs NP is independent of formal logic
Aaronson survey, and Shai Ben-David work
Obstacles to showing P = NP
- Yannakakis's impossibility result for the TSP polytope
- Michael Sipser's (old, circa 1992) review of P vs NP
- Gerhard Woeginger's page on the more 'unusual' P vs NP approaches: up to date through Apr 17, 2009 !
- basic overview of some failed approaches
- Scott Aaronson's truly brilliant analysis of the question: is P vs NP formally independent ?
- hierarchies for probabilistic machines
- Dick Lipton's speculation on another attack on P vs NP