Reversible pebble games and the relation between tree-like and general resolution space

DOI10.1007/s00037-021-00206-1OpenAlexW3158790960MaRDI QIDQ2033469

Florian Wörz, Jacobo Toran

Publication date: 17 June 2021

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-021-00206-1

zbMATH Keywords

resolutionproof complexitytree-like resolutionpebble gameclause spaceprover-delayer gameRaz-Mckenzie gamereversible pebblingvariable space

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Near optimal seperation of tree-like and general resolution
• The depth of resolution proofs
• A combinatorial characterization of treelike resolution space
• A comparison of two variations of a pebble game on graphs
• Extreme time-space tradeoffs for graphs with small space requirements
• The number of registers required for evaluating arithmetic expressions
• On space and depth in resolution
• Cops-robber games and the resolution of Tseitin formulas
• Space bounds for resolution
• Separation of the monotone NC hierarchy
• Nullstellensatz size-degree trade-offs from reversible pebbling
• On the Relative Strength of Pebbling and Resolution
• Space Complexity in Propositional Calculus
• Hard examples for resolution
• Time/Space Trade-Offs for Reversible Computation
• Short proofs are narrow—resolution made simple
• Time and space complexity of reversible pebbling
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

This page was built for publication: Reversible pebble games and the relation between tree-like and general resolution space