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

DOI10.1007/S00037-021-00206-1MaRDI QIDQ2033469zbMATH OpenOpenAlexFDO

Authors Florian Wörz, Jacobo Torán

Publication date 17 June 2021

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

clause spacepebble gameproof complexityprover-delayer gameRaz-Mckenzie gameresolutionreversible pebblingtree-like resolutionvariable space

Mathematics Subject Classification ID

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

Recommendations

• Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
• Space bounds for resolution
• scientific article; zbMATH DE number 1304340
• scientific article; zbMATH DE number 1424047
• A combinatorial characterization of treelike resolution space

Cites work

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

Cited in

(4)

• A game characterisation of tree-like Q-resolution size
• Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
• Pebble games and algebraic proof systems
• Pebble games and algebraic proof systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2033469)