2016 seminar talk: Complexity theory in feasible mathematics
Talk held by Ján Pich (KGRC) at the KGRC seminar on 2016-10-03.
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