Speaker Eli Ben-Sasson
Host Madhu Sudan
Date recorded 26 October 2011
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.
©2011 Microsoft Corporation. All rights reserved.