Lower bounds for the polynomial calculus

DOI10.1007/s000370050013zbMath1026.03043OpenAlexW2093396771WikidataQ56701136 ScholiaQ56701136MaRDI QIDQ1293358

Alexander A. Razborov

Publication date: 7 December 2003

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000370050013

zbMATH Keywords

degreelower boundBoolean functionpigeonhole principleGröbner proofspolynomial calculus proofs

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (24)

Narrow Proofs May Be Maximally Long ⋮ Resolution lower bounds for perfect matching principles ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Proof complexity in algebraic systems and bounded depth Frege systems with modular counting ⋮ Space Complexity in Polynomial Calculus ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Towards NP-P via proof complexity and search ⋮ Algebraic proof systems over formulas. ⋮ Algebraic proofs over noncommutative formulas ⋮ On the automatizability of polynomial calculus ⋮ Unnamed Item ⋮ On the complexity of Hilbert refutations for partition ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity ⋮ Linear gaps between degrees for the polynomial calculus modulo distinct primes ⋮ Unnamed Item ⋮ The Complexity of Propositional Proofs ⋮ Complexity of Null- and Positivstellensatz proofs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Proof Complexity of Non-classical Logics ⋮ Propositional proof complexity ⋮ Reflections on Proof Complexity and Counting Principles

This page was built for publication: Lower bounds for the polynomial calculus