✦ LIBER ✦

Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle

✍ Scribed by Samuel R Buss; Toniann Pitassi

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 377 KB
Volume: 57
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1998.1585

No coin nor oath required. For personal study only.

✦ Synopsis

This paper gives nearly optimal, logarithmic upper and lower bounds on the minimum degree of Nullstellensatz refutations (i.e., polynomials) of the propositional induction principle.