Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs

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

Pavel Pudlák, Russell Impagliazzo, Toniann Pitassi, 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

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, 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., On the complexity of Hilbert refutations for partition, 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, 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