TOC Seminar: Grand Challanges in Complexity Theory through the Lens of Proof Theory

About This Video

Abstract: Given our current inability to even formulate a coherent program towards solving grand challenges in computational complexity (such as P vs. NP), it becomes increasingly important to at least understand this state of affairs; such attempts are often called ``barriers''. The proof-theoretic approach tries to rule out the existence of solutions within a class of methods that is both rigorously defined and reasonably large, in the hope that this will give at least some insight into the nature of the difficulties. It turns out that this approach becomes most successful when the class of methods inherently involves, explicitly or implicitly, computational concepts similar to those it intends to study. One framework where this hope has materialized is called Natural Proofs, and the parallel framework in which the corresponding problems are largely open is that of (propositional) proof complexity. The main purpose of this talk is to give an accessible introduction to this kind of problems, in the hope of attracting to them new generation of researchers.