Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs

DOI10.1112/plms/s3-73.1.1zbMath0853.03017WikidataQ106785076 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

68Q25: Analysis of algorithms and problem complexity

03F30: First-order arithmetic and fragments

03B05: Classical propositional logic

03F20: Complexity of proofs

Related Items

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