The depth of resolution proofs
From MaRDI portal
Publication:647405
DOI10.1007/S11225-011-9356-9zbMATH Open1259.03074OpenAlexW2083975113MaRDI QIDQ647405FDOQ647405
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
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- Short proofs are narrow—resolution made simple
- A combinatorial characterization of treelike resolution space
- An exponential separation between regular and general resolution
- The Complexity of Propositional Proofs
- Title not available (Why is that?)
- Space Complexity in Propositional Calculus
- Title not available (Why is that?)
- Title not available (Why is that?)
- Near optimal seperation of tree-like and general resolution
- Space bounds for a game on graphs
- Space bounds for resolution
- On the complexity of resolution with bounded conjunctions
- Separation of the monotone NC hierarchy
- On the relative complexity of resolution refinements and cutting planes proof systems
- Narrow proofs may be spacious
- Regular and General Resolution: An Improved Separation
- Size space tradeoffs for resolution
- Search Problems in the Decision Tree Model
Cited In (8)
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Understanding Resolution Proofs through Herbrand’s Theorem
- Reversible pebble games and the relation between tree-like and general resolution space
- Resolution over linear equations modulo two
- Theory and Applications of Satisfiability Testing
- A Logical Autobiography
- Cutting planes width and the complexity of graph isomorphism refutations
- On space and depth in resolution
Recommendations
This page was built for publication: The depth of resolution proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q647405)
