Tradeoffs Between Fundamental Complexity Measures of Propositional Proofs

Опубликовано 17 августа 2016, 3:45

What kind of theorems are easy to state yet hard to prove? This question motivates the study of propositional proof complexity. In this introductory talk I will describe the three fundamental proof-complexity measures of proof length, width, and space. These measures correspond to different aspects of the ``hardness'' of proving a given theorem. Then I will discuss the surprising relationships between these three measures and conclude with accessible and intriguing open questions in this area. Based on joint work with Jakob Nordstrom.