A Framework for Space Complexity in Algebraic Proof Systems
From MaRDI portal
Publication:2796410
DOI10.1145/2699438zbMath1333.03238OpenAlexW2217204207WikidataQ61732564 ScholiaQ61732564MaRDI QIDQ2796410
Ilario Bonacina, Nicola Galesi
Publication date: 24 March 2016
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2699438
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
Narrow Proofs May Be Maximally Long ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Space proof complexity for random 3-CNFs ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Total Space in Resolution
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Random CNF's are hard for the polynomial calculus
- Lower bounds for the polynomial calculus
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Space bounds for resolution
- On the complexity of resolution with bounded conjunctions
- An exponential separation between the parity principle and the pigeonhole principle
- On the automatizability of polynomial calculus
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Space proof complexity for random 3-CNFs
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- A combinatorial characterization of resolution width
- Total Space in Resolution
- Optimality of size-degree tradeoffs for polynomial calculus
- Pseudo-partitions, transversality and locality
- Space Complexity in Propositional Calculus
- Many hard examples for resolution
- The relative efficiency of propositional proof systems
- Short proofs are narrow—resolution made simple
- Space complexity of random formulae in resolution
- Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
- Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
- On sufficient conditions for unsatisfiability of random formulas
- A Machine-Oriented Logic Based on the Resolution Principle
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
This page was built for publication: A Framework for Space Complexity in Algebraic Proof Systems
