Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CLAUSE SPACE:
Reports tagged with Clause Space:
TR19-097 | 4th July 2019
Jacobo Toran, Florian Wörz

Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

Comments: 1

We show a new connection between the space measure in tree-like resolution and the reversible pebble game in graphs. Using this connection we provide several formula classes for which there is a logarithmic factor separation between the space complexity measure in tree-like and general resolution. We show that these separations ... more >>>




ISSN 1433-8092 | Imprint