Proof complexity of circuit lower bounds
Seminar Room 1, Newton Institute
AbstractTechniques that could resolve P vs. NP are considerably restricted by well-known barriers in computational complexity. There are several corresponding results in logic stating that certain fragments of arithmetic are not sufficiently strong to prove that P differs from NP or some similar conjectures. We investigate possible extensions of these barriers to stronger theories. Mainly, Razborov's conjecture about hardness of Nisan-Wigderson generators for Extended Frege systems and natural proofs in proof systems admitting feasible disjunction property pointed out by Rudich.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.