Good degree bounds on Nullstellensatz refutations of the induction principle

DOI10.1006/jcss.1998.1585zbMath0921.68088OpenAlexW2020513176MaRDI QIDQ1276164

Toniann Pitassi, Samuel R. Buss

Publication date: 29 September 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1585

zbMATH Keywords

Nullstellensatz refutations

Mathematics Subject Classification ID

Related Items (5)

Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz ⋮ Linear gaps between degrees for the polynomial calculus modulo distinct primes ⋮ The Complexity of Propositional Proofs ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling

Cites Work

• The intractability of resolution
• Bounds for the degrees in the Nullstellensatz
• Sharp Effective Nullstellensatz
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Good degree bounds on Nullstellensatz refutations of the induction principle