The depth of resolution proofs
type: Item
instance of: scholarly article
title: The depth of resolution proofs
zbMATH Open document ID: 1259.03074
author: Alasdair Urquhart
published in: Studia Logica
publication date: 2011-11-23T00:00:00Z
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 5977614
zbMATH Keywords: resolution proofs
zbMATH Keywords: depth of proofs
zbMATH Keywords: proof complexity
MaRDI profile type: Publication
full work available at URL: s11225-011-9356-9
OpenAlex ID: W2083975113
cites work: An exponential separation between regular and general resolution
cites work: Space Complexity in Propositional Calculus
cites work: Size space tradeoffs for resolution
cites work: Near optimal seperation of tree-like and general resolution
cites work: Short proofs are narrow—resolution made simple
cites work: On the relative complexity of resolution refinements and cutting planes proof systems
cites work: A combinatorial characterization of treelike resolution space
cites work: On the complexity of resolution with bounded conjunctions
cites work: Space bounds for resolution
cites work: Search Problems in the Decision Tree Model
cites work: Narrow proofs may be spacious
cites work: Space bounds for a game on graphs
cites work: Q4952609
cites work: Separation of the monotone NC hierarchy
cites work: Q4344138
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Q3682462
cites work: The Complexity of Propositional Proofs
cites work: Regular and General Resolution: An Improved Separation
DOI: 10.1007/S11225-011-9356-9
description: scientific article; zbMATH DE number 5977614