Reversible pebble games and the relation between tree-like and general resolution space
type: Item
instance of: scholarly article
title: Reversible pebble games and the relation between tree-like and general resolution space
author: Florian Wörz
author: Jacobo Torán
published in: Computational Complexity
publication date: 2021-06-17T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7360377
zbMATH Keywords: proof complexity
zbMATH Keywords: resolution
zbMATH Keywords: tree-like resolution
zbMATH Keywords: pebble game
zbMATH Keywords: reversible pebbling
zbMATH Keywords: prover-delayer game
zbMATH Keywords: Raz-Mckenzie game
zbMATH Keywords: clause space
zbMATH Keywords: variable space
MaRDI profile type: Publication
full work available at URL: s00037-021-00206-1
OpenAlex ID: W3158790960
cites work: Space Complexity in Propositional Calculus
cites work: Near optimal seperation of tree-like and general resolution
cites work: Short proofs are narrow—resolution made simple
cites work: Time/Space Trade-Offs for Reversible Computation
cites work: Extreme time-space tradeoffs for graphs with small space requirements
cites work: A machine program for theorem-proving
cites work: A Computing Procedure for Quantification Theory
cites work: Nullstellensatz size-degree trade-offs from reversible pebbling
cites work: Space bounds for resolution
cites work: A combinatorial characterization of treelike resolution space
cites work: The number of registers required for evaluating arithmetic expressions
cites work: Cops-robber games and the resolution of Tseitin formulas
cites work: Time and space complexity of reversible pebbling
cites work: A comparison of two variations of a pebble game on graphs
cites work: On the Relative Strength of Pebbling and Resolution
cites work: Q4185781
cites work: Q4952609
cites work: Separation of the monotone NC hierarchy
cites work: On space and depth in resolution
cites work: Q4945238
cites work: Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
cites work: Q5593816
cites work: Hard examples for resolution
cites work: The depth of resolution proofs
DOI: 10.1007/S00037-021-00206-1
description: scientific article; zbMATH DE number 7360377