# P vs NP

### From ResearchWiki

**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 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 | |

Jul 20 | Algebrization |

# 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.

##### 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

## 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