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

# 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)
June 15 June 18 June 22 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.

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

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

• Proof Complexity; lower bounds for resolution proofs

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