Title :
Good degree bounds on Nullstellensatz refutations of the induction principle
Author :
Buss, Samuel R. ; Pitassi, Toniann
Author_Institution :
Dept. of Math., California Univ., San Diego, La Jolla, CA, USA
Abstract :
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
Keywords :
computational complexity; theorem proving; Nullstellensatz refutations; degree bounds; induction principle; lower bounds; minimum degree; proof system; propositional induction principle; upper bounds; Automatic testing; Computer science; Equations; Mathematics; Polynomials; System testing;
Conference_Titel :
Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
Conference_Location :
Philadelphia, PA
Print_ISBN :
0-8186-7386-9
DOI :
10.1109/CCC.1996.507685
