License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.60
URN: urn:nbn:de:0030-drops-119213
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11921/
Go to the corresponding LIPIcs Volume Portal

Torán, Jacobo ; Wörz, Florian

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

pdf-format:
LIPIcs-STACS-2020-60.pdf (0.6 MB)

Abstract

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 not far from 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 space is upper bounded by space(π)log(time(π)), where π is any general resolution refutation of F. This holds considering as space(π) 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(π)log n, where n is the number of vertices of the corresponding graph.

BibTeX - Entry

@InProceedings{torn_et_al:LIPIcs:2020:11921,
  author =	{Jacobo Tor{\'a}n and Florian W{\"o}rz},
  title =	{{Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11921},
  URN =		{urn:nbn:de:0030-drops-119213},
  doi =		{10.4230/LIPIcs.STACS.2020.60},
  annote =	{Keywords: Proof Complexity, Resolution, Tree-like Resolution, Pebble Game, Reversible Pebbling, Prover-Delayer Game, Raz - McKenzie Game, Clause Space, Variable Space}
}

Keywords: Proof Complexity, Resolution, Tree-like Resolution, Pebble Game, Reversible Pebbling, Prover-Delayer Game, Raz - McKenzie Game, Clause Space, Variable Space
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI