Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
From MaRDI portal
Publication:6168323
DOI10.1016/j.jcss.2023.04.006MaRDI QIDQ6168323
Theodoros Papamakarios, Alexander A. Razborov
Publication date: 10 July 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Near optimal seperation of tree-like and general resolution
- The depth of resolution proofs
- On generalized Horn formulas and \(k\)-resolution
- A combinatorial characterization of treelike resolution space
- Storage requirements for deterministic polynomial time recognizable languages
- Optimality of size-width tradeoffs for resolution
- On space and depth in resolution
- A note about \(k\)-DNF resolution
- Space bounds for resolution
- On the complexity of resolution with bounded conjunctions
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- A combinatorial characterization of resolution width
- On the weak pigeonhole principle
- Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- Space Complexity in Propositional Calculus
- A New Kind of Tradeoffs in Propositional Proof Complexity
- Unified Characterisations of Resolution Hardness Measures
- Size-Space Tradeoffs for Resolution
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Space bounds for a game on graphs
- The relative efficiency of propositional proof systems
- Lower bounds to the size of constant-depth propositional proofs
- Short proofs are narrow—resolution made simple
- Communication Lower Bounds via Critical Block Sensitivity
- Total Space in Resolution Is at Least Width Squared
- Proof Complexity
- Lifting Theorems for Equality
- From Small Space to Small Width in Resolution
- On the virtue of succinct proofs
- Some trade-off results for polynomial calculus
- Theory and Applications of Satisfiability Testing
This page was built for publication: Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
