Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
2021
We show a new connection between the clause space measure in tree-like resolution and the reversible pebble game on graphs.
Using this connection, we provide several formula classes for which there is a logarithmic factor separation between the clause space complexity measure in tree-like and general resolution.
We also provide upper bounds
for tree-like resolution clause space in terms of general resolution
clause and variable space. In particular, we show that for
any formula F, its tree-like resolution clause space is upper bounded
by space
$$(\pi)$$
$$(\log({\rm time}(\pi))$$
, 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
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
32
References
1
Citations
NaN
KQI