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

DOI10.1016/J.JCSS.2023.04.006MaRDI QIDQ6168323zbMATH OpenFDO

Authors Theodoros Papamakarios, Alexander Razborov

Publication date 10 July 2023

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

Full work available at URL https://doi.org/10.1016/J.JCSS.2023.04.006

zbMATH Keywords

proof complexityresolutionsize-space trade-offs

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

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

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)