Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with EXPTIME-Completeness:
TR06-133 | 14th October 2006
Alex Hertel, Alasdair Urquhart

The Resolution Width Problem is EXPTIME-Complete

The importance of {\em width} as a resource in resolution theorem proving
has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower
bounds on the size of resolution refutations can be proved in a uniform manner by
demonstrating lower bounds on the width ... more >>>

ISSN 1433-8092 | Imprint