The depth of resolution proofs
From MaRDI portal
Publication:647405
DOI10.1007/s11225-011-9356-9zbMath1259.03074OpenAlexW2083975113MaRDI QIDQ647405
Publication date: 23 November 2011
Published in: Studia Logica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11225-011-9356-9
Related Items (5)
On space and depth in resolution ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Reversible pebble games and the relation between tree-like and general resolution space ⋮ Resolution over linear equations modulo two ⋮ A Logical Autobiography
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Near optimal seperation of tree-like and general resolution
- A combinatorial characterization of treelike resolution space
- Space bounds for resolution
- On the complexity of resolution with bounded conjunctions
- Separation of the monotone NC hierarchy
- Relationships between nondeterministic and deterministic tape complexities
- On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
- Narrow proofs may be spacious
- Space Complexity in Propositional Calculus
- Regular and General Resolution: An Improved Separation
- An exponential separation between regular and general resolution
- Size space tradeoffs for resolution
- Space bounds for a game on graphs
- Short proofs are narrow—resolution made simple
- Search Problems in the Decision Tree Model
- The Complexity of Propositional Proofs
This page was built for publication: The depth of resolution proofs
