The polynomial bound on integer zeros of straight-line computable polynomials
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.