Event Detail

What is the bound on the length of possible proofs of propositional formulas? Is P = NP? These questions, while deceptively simple to state, have eluded over half a century of concerted effort to resolve them. Could it be that the complexity of the meta-problem, of proving such computational complexity statements, is itself high – in a formal logical sense? In this talk, I will survey what is known about the complexity of reasoning about computational complexity, in particular in the setting of bounded arithmetic, including exciting new results that appeared in the last several years.