The depth of resolution proofs
From MaRDI portal
Publication:647405
Recommendations
Cites work
- scientific article; zbMATH DE number 3904558 (Why is no real title available?)
- scientific article; zbMATH DE number 1033441 (Why is no real title available?)
- scientific article; zbMATH DE number 1445296 (Why is no real title available?)
- A combinatorial characterization of treelike resolution space
- An exponential separation between regular and general resolution
- Narrow proofs may be spacious, separating space and width in resolution
- Near optimal seperation of tree-like and general resolution
- On the complexity of resolution with bounded conjunctions
- On the relative complexity of resolution refinements and cutting planes proof systems
- Regular and General Resolution: An Improved Separation
- Relationships between nondeterministic and deterministic tape complexities
- Search Problems in the Decision Tree Model
- Separation of the monotone NC hierarchy
- Short proofs are narrow—resolution made simple
- Size space tradeoffs for resolution
- Space Complexity in Propositional Calculus
- Space bounds for a game on graphs
- Space bounds for resolution
- The Complexity of Propositional Proofs
Cited in
(10)- Resolution over linear equations modulo two
- A Logical Autobiography
- Reversible pebble games and the relation between tree-like and general resolution space
- Theory and Applications of Satisfiability Testing
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Understanding Resolution Proofs through Herbrand’s Theorem
- Proof complexity and textual cohesion
- On space and depth in resolution
- Cutting planes width and the complexity of graph isomorphism refutations
- Preliminary Report on Input Cover Number as a Metric for Propositional Resolution Proofs
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)