Space complexity in polynomial calculus
From MaRDI portal
Classical propositional logic (03B05) Mechanization of proofs and logical operations (03B35) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Recommendations
Cites work
- A combinatorial characterization of resolution width
- A Computing Procedure for Quantification Theory
- A generalized method for proving polynomial calculus degree lower bounds
- A machine program for theorem-proving
- A Machine-Oriented Logic Based on the Resolution Principle
- A simplified way of proving trade-off results for resolution
- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
- Communication lower bounds via critical block sensitivity
- GRASP: a search algorithm for propositional satisfiability
- Hard examples for resolution
- scientific article; zbMATH DE number 1223618 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1263234 (Why is no real title available?)
- scientific article; zbMATH DE number 6829289 (Why is no real title available?)
- scientific article; zbMATH DE number 2134905 (Why is no real title available?)
- scientific article; zbMATH DE number 2174386 (Why is no real title available?)
- scientific article; zbMATH DE number 5493266 (Why is no real title available?)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower bounds for the polynomial calculus
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas
- Many hard examples for resolution
- Narrow proofs may be spacious: separating space and width in resolution
- New developments in the theory of Gröbner bases and applications to formal verification
- On the complexity of cutting-plane proofs
- On the power of clause-learning SAT solvers as resolution engines
- On the virtue of succinct proofs
- Pebble games, proof complexity, and time-space trade-offs
- Polybori: A framework for Gröbner-basis computations with Boolean polynomials
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- Random CNF's are hard for the polynomial calculus
- Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning
- Short proofs are narrow—resolution made simple
- Size-space tradeoffs for resolution
- Some trade-off results for polynomial calculus (extended abstract)
- Space bounds for resolution
- Space Complexity in Propositional Calculus
- Space complexity of random formulae in resolution
- Space proof complexity for random 3-CNFs
- The Complexity of Propositional Proofs
- The efficiency of resolution and Davis-Putnam procedures
- The intractability of resolution
- The relative efficiency of propositional proof systems
- Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
- 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
(17)- Degree complexity for a modified pigeonhole principle
- On semantic cutting planes with very small coefficients
- scientific article; zbMATH DE number 1670882 (Why is no real title available?)
- Total space in resolution
- A Note on the Space Complexity of Fast D-Finite Function Evaluation
- Optimality of size-degree tradeoffs for polynomial calculus
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- Space Complexity in Propositional Calculus
- Space complexity in propositional calculus
- Cumulative space in black-white pebbling and resolution
- Resolution and the binary encoding of combinatorial principles
- From small space to small width in resolution
- Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
- Some trade-off results for polynomial calculus (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: Space complexity in polynomial calculus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944568)
