Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial can be made exponentially large by repeated squaring. This question addresses the issue of how to work around this and keep the problem in randomized polynomial time.
On the other hand, when the problem is initially presented (e.g. here), it is often illustrated over arithmetic expressions containing only constants, variables, addition, and multiplication. Such polynomials have total degree at most polynomial in the length of the input expression, and for any such polynomial the size of the output value is polynomial in the size of the input values. But since a polynomial of degree $d$ has at most $d$ roots, isn't this trivial? Just evaluate the polynomial over the rationals at any $d + 1$ distinct points and check whether the result is zero at each point. This should take only polynomial time. Is this correct? If so, why are arithmetic expressions without shared subexpressions often used as examples, when sharing is essential to the difficulty of the problem?
Asked By : Aaron Rotenberg
Answered By : Ricky Demer
That isn't known to be trivial.
The polynomial $x \cdot y$ has infinitely many roots. (When either variable is zero, the other variable won't affect the polynomial's value.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/51895
0 comments:
Post a Comment
Let us know your responses and feedback