Previous slide Next slide Back to the first slide View text version


Notes:

Has led to many interesting combinatorial questions and some oracle results.

Razborov - Monotone techniques will not carry over to nonmonotone world.

Razborov - In small fragment of arithmetic strong enough to prove favorite theorems 2 & 3, cannot show NP does not have poly size circuits.

Razborov-Rudich - Under strong crypto assumption, combinatorial proofs fulfilling certain largeness and constructivity properties cannot show NP does not have poly size circuits.