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)

zbMATH Keywords

resolutionproof complexitysize-space trade-offs

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 1445296 (Why is no real title available?)
• 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
• 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 Complexity in Propositional Calculus
• Space bounds for a game on graphs
• Space bounds for resolution
• 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)