A framework for space complexity in algebraic proof systems
From MaRDI portal
Recommendations
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- scientific article; zbMATH DE number 512803
- Efficient rational proofs for space bounded computations
- Space complexity in propositional calculus
- Space Complexity in Propositional Calculus
- Time-space tradeoffs in algebraic complexity theory
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- scientific article; zbMATH DE number 2086404
- Proof systems for structured algebraic specifications: An overview
- scientific article; zbMATH DE number 4114007
Cites work
- A combinatorial characterization of resolution width
- A Machine-Oriented Logic Based on the Resolution Principle
- An exponential separation between the parity principle and the pigeonhole principle
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1114028 (Why is no real title available?)
- scientific article; zbMATH DE number 2174386 (Why is no real title available?)
- scientific article; zbMATH DE number 967945 (Why is no real title available?)
- scientific article; zbMATH DE number 3029852 (Why is no real title available?)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Lower bounds for the polynomial calculus
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Many hard examples for resolution
- Narrow proofs may be spacious: separating space and width in resolution
- On sufficient conditions for unsatisfiability of random formulas
- On the automatizability of polynomial calculus
- On the complexity of resolution with bounded conjunctions
- Optimality of size-degree tradeoffs for polynomial calculus
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Random CNF's are hard for the polynomial calculus
- Short proofs are narrow—resolution made simple
- Space bounds for resolution
- Space Complexity in Propositional Calculus
- Space complexity of random formulae in resolution
- Space proof complexity for random 3-CNFs
- The relative efficiency of propositional proof systems
- Total space in resolution
- Towards an optimal separation of space and length in resolution
- Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
Cited in
(15)- Efficient rational proofs for space bounded computations
- Space-efficient fragments of higher-order fixpoint logic
- Space proof complexity for random 3-CNFs
- Proof spaces for unbounded parallelism
- Total space in resolution
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- Computational Space Efficiency and Minimal Model Generation for Guarded Formulae
- scientific article; zbMATH DE number 2081098 (Why is no real title available?)
- Cumulative space in black-white pebbling and resolution
- Resolution and the binary encoding of combinatorial principles
- Narrow proofs may be maximally long
- Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
- Proof complexity and the binary encoding of combinatorial principles
- Polynomial calculus space and resolution width
- Towards an understanding of polynomial calculus: new separations and lower bounds
This page was built for publication: A framework for space complexity in algebraic proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796410)
