Open Collections

Reversible Pebble Games and the Relation between Tree-like and General Resolution

Banff International Research Station for Mathematical Innovation and Discovery

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 are almost optimal by proving upper bounds for tree-like resolution space in terms of general resolution clause and variable space. In particular we show that for any formula $F$, its tree-like resolution is upper bounded by space$(\pi)\big(\hbox{\rm time}(\pi)\big)$ where $\pi$ is any general resolution refutation of $F$. This holds considering as space$(\pi)$ the clause space of the refutation as well as considering its variable space. For the concrete case of Tseitin formulas we are able to improve this bound to the optimal bound space$(\pi)\log n$, where $n$ is the number of vertices of the corresponding graph.

Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science

video/mp4

Author affiliation: University of Ulm

2020-07-22

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/75236

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/