Abstract:
Propositional proof complexity studies efficient provability of quantifier-free statements in various proof systems and under various notions of efficiency. In this talk I will attempt to convey some of its basic concepts, ideas and results, including numerous connections to other areas in logic, theoretical computer science and beyond.
Contact us: