Isn't polynomial identity testing over arithmetic *expressions* trivial?

Question

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?

Answer 1

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.)

Answer 2

For a univariate polynomial $p(x)$, yes, it's that easy.

For a multivariate polynomial $p(x_1,x_2,\dots,x_k)$, no, no such algorithm works.

In particular, when you write "a polynomial of degree $d$ has at most $d$ roots", that is true for univariate polynomials $p(x)$, but it is not true in general for multivariate polynomials. Ricky Demer gives a simple example: $p(x,y) = xy$ is of degree two, but has infinitely many roots.

Answer 3

heres a more general/ abstract way to understand the significance/ hardness of polynomial identity testing in CS. one reason polynomial identity testing is under intense study right now because it has long been known to be closely linked to boolean circuit complexity. imagine taking two arbitrary boolean circuits and then converting them (ie basically setting up a 1-1 mapping) to multivariate polynomials. this is not so hard. basically one uses values of 0/1 to represent false/ true and the constructions are set up in old papers. then the roots of the polynomial correspond to T/F variable assignments that satisfy the formulas/ circuits.

after this setup, PIT is basically nearly the same problem as determining if two binary circuits are equivalent. there are also other (newer) deep proofs that say its nearly equivalent in complexity to factoring polynomials.[1] so one ends up with a result like the following: if one can solve PIT "quickly" it means that two large circuits can be compared for equivalence "quickly" which is unlikely. so a rough way to understand the problem is that its nearly equivalent to nontrivial problems in boolean circuit theory.