Alladi Ramakrishnan Hall

Godel's Theorem and Propositional Proof Complexity

Rahul Santhanam

Oxford, UK

A classical result of Godel states that for any 'rich enough' consistent first-order theory T of arithmetic, there are statements that are true in the natural numbers but are unprovable in T.

Are there analogues of this result for the finitistic setting of propositional proof complexity? And might such analogues have implications for the hardness of showing complexity lower bounds?

I will discuss some recent results with Jan Pich on these questions.