Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle

摘要

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