Complexity of Null- and Positivstellensatz proofs

DOI10.1016/S0168-0072(01)00055-0zbMath0992.03073OpenAlexW2078561631MaRDI QIDQ5957910

Dima Yu. Grigoriev, Nikolaj N. jun. Vorob'ev

Publication date: 13 March 2002

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(01)00055-0

zbMATH Keywords

lower boundsproof systemspolynomial calculuslengths of derivationsproof complexity

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (25)

Narrow Proofs May Be Maximally Long ⋮ Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization ⋮ Limitations of Algebraic Approaches to Graph Isomorphism Testing ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ SOS Is Not Obviously Automatizable, Even Approximately ⋮ Unnamed Item ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ Tight size-degree bounds for sums-of-squares proofs ⋮ Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem ⋮ Algebraic proof systems over formulas. ⋮ Unnamed Item ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Tropical effective primary and dual Nullstellensätze ⋮ Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity ⋮ Unnamed Item ⋮ Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares ⋮ Subtraction-free complexity, cluster transformations, and spanning trees ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph

Cites Work

• Unnamed Item
• Unnamed Item
• Bounds for the degrees in the Nullstellensatz
• Lower bounds for the polynomial calculus
• Stable sets and polynomials
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• The Positivstellensatz and Small Deduction Rules for Systems of Inequalities
• 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 Positivstellensatz proofs for the knapsack

This page was built for publication: Complexity of Null- and Positivstellensatz proofs