P vs NP
From ResearchWiki
(Difference between revisions)
(→Attempt 2: Circuit lower bounds) |
(→Participants) |
||
| Line 14: | Line 14: | ||
* [http://www.cs.utah.edu/~alfeld Scott Alfeld], MS Student, School of Computing | * [http://www.cs.utah.edu/~alfeld Scott Alfeld], MS Student, School of Computing | ||
* [mailto:avishek@cs.utah.edu Avishek Saha], PhD Student, School of Computing | * [mailto:avishek@cs.utah.edu Avishek Saha], PhD Student, School of Computing | ||
| + | * [http://www.cs.utah.edu/~seth Seth Juarez], PhD Student, School of Computing | ||
=Schedule= | =Schedule= | ||
Revision as of 14:38, 1 June 2009
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.
Participants
- 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
Schedule
| Date | Topic | Presenter |
|---|---|---|
| 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 14.1) | |
Outline
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
- Dick Lipton's post on circuit lower bounds
- Timothy Chow's new paper on almost natural proofs.
Lower bounds for SAT
Unnatural non-relativization
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
Readings
- 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
