On space and depth in resolution
type: Item
instance of: scholarly article
title: On space and depth in resolution
published in: Computational Complexity
publication date: 2018-11-07T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6974168
zbMATH Keywords: resolution proofs
zbMATH Keywords: supercritical tradeoff
zbMATH Keywords: variable and total space
author: Alexander Razborov
MaRDI profile type: Publication
full work available at URL: s00037-017-0163-1
OpenAlex ID: W2765538602
cites work: Space Complexity in Propositional Calculus
cites work: Resolution Is Not Automatizable Unless W[P] Is Tractable
cites work: A combinatorial characterization of resolution width
cites work: On the diameter of permutation groups
cites work: Sum-of-squares proofs and the quest toward optimal algorithms
cites work: Some trade-off results for polynomial calculus
cites work: Size-Space Tradeoffs for Resolution
cites work: Short proofs are narrow—resolution made simple
cites work: Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
cites work: Supercritical Space-Width Trade-offs for Resolution
cites work: Total Space in Resolution Is at Least Width Squared
cites work: The relative efficiency of propositional proof systems
cites work: Space bounds for resolution
cites work: From Small Space to Small Width in Resolution
cites work: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
cites work: Pebble games, proof complexity, and time-space trade-offs
cites work: A New Kind of Tradeoffs in Propositional Proof Complexity
cites work: On the Width of Semialgebraic Proofs and Algorithms
cites work: A Machine-Oriented Logic Based on the Resolution Principle
cites work: The depth of resolution proofs
DOI: 10.1007/S00037-017-0163-1
Recommended article: Q3191584
Recommended article: Q4251071
Recommended article: Space bounds for resolution
Recommended article: Q3817284
Recommended article: Notes on resolving resolution dimensions
Recommended article: Size-Space Tradeoffs for Resolution
Recommended article: Resolving resolution dimensions
Recommended article: Total space in resolution
Recommended article: Supercritical Space-Width Trade-offs for Resolution
description: scientific article; zbMATH DE number 6974168