Space characterizations of complexity measures and size-space trade-offs in propositional proof systems

DOI10.1016/J.JCSS.2023.04.006MaRDI QIDQ6168323FDOQ6168323

Authors: Theodoros Papamakarios, Alexander Razborov 

Publication date: 10 July 2023

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

resolutionproof complexitysize-space trade-offs

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Title not available (Why is that?)
• The relative efficiency of propositional proof systems
• Short proofs are narrow—resolution made simple
• A combinatorial characterization of treelike resolution space
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• On the weak pigeonhole principle
• Lower bounds to the size of constant-depth propositional proofs
• Title not available (Why is that?)
• Space Complexity in Propositional Calculus
• Near optimal seperation of tree-like and general resolution
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• Space bounds for a game on graphs
• Space bounds for resolution
• On the complexity of resolution with bounded conjunctions
• The depth of resolution proofs
• On generalized Horn formulas and \(k\)-resolution
• A combinatorial characterization of resolution width
• Storage requirements for deterministic polynomial time recognizable languages
• Proof Complexity
• Communication lower bounds via critical block sensitivity
• Optimality of size-width tradeoffs for resolution
• On space and depth in resolution
• Size-space tradeoffs for resolution
• Lifting Theorems for Equality
• Pebble games, proof complexity, and time-space trade-offs
• A new kind of tradeoffs in propositional proof complexity
• Towards an optimal separation of space and length in resolution
• Total space in resolution is at least width squared
• From small space to small width in resolution
• Some trade-off results for polynomial calculus (extended abstract)
• A note about \(k\)-DNF resolution
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• On the virtue of succinct proofs
• Unified Characterisations of Resolution Hardness Measures
• Theory and Applications of Satisfiability Testing

Cited In (1)

• A framework for space complexity in algebraic proof systems

This page was built for publication: Space characterizations of complexity measures and size-space trade-offs in propositional proof systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168323)