Good Degree Bounds on Nullstellensatz Re
✍
Samuel R Buss; Toniann Pitassi
📂
Article
📅
1998
🏛
Elsevier Science
🌐
English
⚖ 377 KB
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.