Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
    
Ah, okay. Don't know how I missed that multi-variable polynomials can have infinitely many roots. – Aaron Rotenberg Jan 16 at 1:50
    
Incidentally, Corollary 3.1 of this paper gives an interesting consequence for significant (even non-deterministic) improvements on the algorithm you describe. ​ ​ – Ricky Demer Jan 20 at 13:58

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.