Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs

DOI10.1112/plms/s3-73.1.1zbMath0853.03017OpenAlexW2323554188WikidataQ106785076 ScholiaQ106785076MaRDI QIDQ4892411

Toniann Pitassi, Pavel Pudlák, Russell Impagliazzo, Jan Krajíček, P. W. Beame

Publication date: 5 December 1996

Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/plms/s3-73.1.1

zbMATH Keywords

algebraic closure modular counting principle Frege proofs algebraic equations over a field independence results for counting principles lower bound on the degrees of polynomials weak form of Hilbert's Nullstellensatz

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) First-order arithmetic and fragments (03F30) Classical propositional logic (03B05) Complexity of proofs (03F20)

Related Items (38)

Limitations of Algebraic Approaches to Graph Isomorphism Testing ⋮ Unnamed Item ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ Proof complexity in algebraic systems and bounded depth Frege systems with modular counting ⋮ \(\text{Count}(q)\) does not imply \(\text{Count}(p)\) ⋮ Lov\'asz Meets Weisfeiler and Leman ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Sharp Effective Finite-Field Nullstellensatz ⋮ Towards NP-P via proof complexity and search ⋮ Algebraic proof systems over formulas. ⋮ Propositional proofs and reductions between NP search problems ⋮ Proof Complexity Meets Algebra ⋮ Unnamed Item ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Propositional proof systems based on maximum satisfiability ⋮ Formal Verification of Integer Multiplier Circuits Using Algebraic Reasoning: A Survey ⋮ On the complexity of Hilbert refutations for partition ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Uniformly generated submodules of permutation modules over fields of characteristic 0. ⋮ Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity ⋮ Linear gaps between degrees for the polynomial calculus modulo distinct primes ⋮ Several notes on the power of Gomory-Chvátal cuts ⋮ Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies ⋮ Complexity of Null- and Positivstellensatz proofs ⋮ Phase transition of multivariate polynomial systems ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ Proof Complexity of Non-classical Logics ⋮ Propositional proof complexity ⋮ Conservative Retractions of Propositional Logic Theories by Means of Boolean Derivatives: Theoretical Foundations ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ On transformations of constant depth propositional proofs ⋮ Separation results for the size of constant-depth propositional proofs ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Another look at degree lower bounds for polynomial calculus ⋮ Reflections on Proof Complexity and Counting Principles

This page was built for publication: Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs