skip to content
 

Separations between propositional proof systems related to clause learning

Presented by: 
J Johannsen Ludwig-Maximilians-Universität München
Date: 
Wednesday 28th March 2012 - 10:00 to 10:30
Venue: 
INI Seminar Room 1
Abstract: 
Resolution trees with lemmas (RTL) are a resolution-based propositional proof system that is related to the DLL algorithm with clause learning, with its fragments RTL(k) being related to clause learning algorithms where the width of learned clauses is bounded by k.

For every k up to O(log n), an exponential separation between the proof systems RTL(k) and RTL(k+1) is shown, indicating that a minimal increase in the width of learned clauses can lead to an exponential speed-up for clause learning algorithms.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons