2016 seminar talk: Complexity theory in feasible mathematics

Talk held by Ján Pich (KGRC) at the KGRC seminar on 2016-10-03.

Abstract

We investigate the provability of conjectures from complexity theory in theories of bounded arithmetic.

As we will see, this is closely related to the central problems in proof complexity like lower bounds on the lengths of proofs in Frege systems and, in particular, to Razborov's conjecture about Nisan-Wigderson generators which gives us candidate hard tautologies for strong proof systems. Additionally, we will show that quasi-polynomial circuit lower bounds for SAT are unprovable in the theory $V^0$.

Time and Place

Tea at 3:30pm in the KGRC meeting room

Talk at 4:00pm in the KGRC lecture room

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.