The polynomial bound on integer zeros of straight-line computable polynomials

From papers

Let a straight-line program for a polynomial in one variable be a list

s0=1,s1=x,s2,,sτ,s_0=1,\quad s_1=x,\quad s_2,\ldots,s_{\tau},

where each sis_i, for i2i\geq 2, is one of sj+sks_j+s_k, sjsks_j-s_k, or sjsks_js_k for some j,k<ij,k<i. For fZ[x]f\in\mathbb Z[x], let τ(f)\tau(f) be the least length of a straight-line program computing ff, and let n(f)n(f) denote the number of distinct integer zeros of ff. Integer-zero bound conjecture. There is a constant a>0a>0 such that, for every univariate polynomial fZ[x]f\in\mathbb Z[x],

n(f)<τ(f)a.n(f)<\tau(f)^a.

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 C\mathbb C 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

No solutions have been posted yet.