Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Tradeoffs Between Fundamental Complexity Measures of Propositional Proofs

Speaker  Eli Ben-Sasson

Affiliation  Technion

Host  Madhu Sudan

Duration  01:11:25

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.
> Tradeoffs Between Fundamental Complexity Measures of Propositional Proofs