Abstract
Sasha Razborov
Title: P, NP and Proof Complexity
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.
Pavel Pudlak
Title: TAUT, TFNP and SAT
Abstract: I will mention connections between the assumptions that these classes do not have complete problems and explain relevance of them to formal arithmetic.
Shai Ben-David
Title: Can the PvsNP Question Be Independent of the Axioms of Mathematical Reasoning?
Abstract: Why do we fail to resolve basic computational complexity questions? Could it be that the P vs NP issue is "un-resolvable"? More concretely: Is it likely that the tools of our mathematical reasoning are inherently too weak to determine relationships between complexity classes?
Should we direct our efforts to answering these logic-oriented questions rather than struggle with the computational complexity questions themselves?
In this talk I will explain an old result of mine showing that proving such logical independence is in a way equivalent to answering the original computational complexity question.