The polynomial bound on integer zeros of straight-line computable polynomials
The polynomial bound on integer zeros of straight-line computable polynomials
Let a straight-line program for a polynomial in one variable be a list
where each , for , is one of , , or for some . For , let be the least length of a straight-line program computing , and let denote the number of distinct integer zeros of . Integer-zero bound conjecture. There is a constant such that, for every univariate polynomial ,
Such a bound would connect the arithmetic complexity of straight-line programs with the number of integer roots and is presented in the context of complexity over and the separation of polynomial-time and nondeterministic polynomial-time computation.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Gregorio Malajovich, “Ultimate Polynomial Time”, arXiv:math/9904130 (1999).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.