11
$\begingroup$

This question must be well known but I cannot find it in the literature.

Question: What is the computational complexity of the word problem in a subring of the ring of polynomials in $n\ge 1$ variables ring over rationals? Is it in $P$?

Thus we fix $m$ polynomials $f_1,...,f_m$ from $\mathbb{Q}[x_1,...,x_n]$ Then for every polynomial $g(y_1,...,y_m)$ over $\mathbb{Q}$, we need to check if the polynomial $g(f_1,...,f_m)$ is 0. The size of the input is the amount of space needed to write down $g$.

Update I was thinking about the following algorithm: we need to check that $g(f_1,...,f_m)=0$. First plug in $x_i=0$ and check that the result is 0. It is easy. Then take the derivative $\partial g(f_1,...,f_m)/\partial x_i$ and plug in 0's there, etc. The number of possible derivatives is polynomial in the size of $g$, and the length of the computation seems to be polynomial in the size of $g$ also. We need to pre-compute enough products of values of $f_i$ and their derivatives at 0. Does this algorithm ran in polynomial time? Is it well-known, and if so what is a reference?

$\endgroup$
6
  • 2
    $\begingroup$ How is g given? That is, is it given as an arithmetic circuit, as an arithmetic formula, or as a sum of monomials? If g is given as an arithmetic circuit or an arithmetic formula, I believe that it is not known to be in NP. See also Kabanets and Impagliazzo 2004 (dx.doi.org/10.1007/s00037-004-0182-6). $\endgroup$ Nov 7, 2011 at 23:24
  • $\begingroup$ @Tsuyoshi: $g$ is given as a sum of monomials, each coefficient and each exponent is in binary. $\endgroup$
    – user6976
    Nov 7, 2011 at 23:53
  • 1
    $\begingroup$ My memory says there is a quick probabilistic algorithm and no known poly-time algorithms. I recall a problem as trying to determine the rank of a matrix of polynomials, and that plugging in values at random and then evaluating was more successful than an attempt at computing the determinant symbolically, even for small orders. If you get no satisfactory answers, I suggest searching for "symbolic computation of determinants", or words to that effect. Or you could ask Manuel Blum: I heard of it from him. Gerhard "It's Wonderful To Remember Anything" Paseman, 2011.11.07 $\endgroup$ Nov 8, 2011 at 1:51
  • $\begingroup$ @Gerhard: I think that you are talking about the identity test for polynomials given as arithmetic formulas (or circuits). If g were given as an arithmetic formula, the identity test for arithmetic formula could be reduced to the current problem and therefore we could conclude that the current problem is not known to be in NP. But because g is given as a sum of monomials (see Mark’s comment), this argument does not hold. (Note that the identity test for polynomials given as sums of monomials is trivial to solve, so we cannot say anything by reducing it to the current problem.) $\endgroup$ Nov 8, 2011 at 21:07
  • 2
    $\begingroup$ Gerhard is correct. See citeseerx.ist.psu.edu/viewdoc/… by Ibarra and Moran. $\endgroup$ Nov 10, 2011 at 3:32

1 Answer 1

5
$\begingroup$

I'm going to summarize what is said in the comments and my own remarks about the update, to make a complete answer:

The algorithm suggested in the update is basically checking lower-order coefficients of the composition. Certainly if the exponents are in binary, then the algorithm doesn't work: It takes exponential time to distinguish $x^n$ from $0$. Even if the exponents are in unary, it takes exponential time to distinguish $x_1x_2\ldots x_n$ from $0$.

The paper of Ibarra and Moran places a more general problem, the word problem in the sense of circuits or straight-line programs, in co-RP.

A straight-line program is a sequence of formulas arranged like a tax form. It's a sequence of intermediate variables defined by formulas. It's equivalent to an arithmetic circuit. It's an interesting definition for groups as well as for polynomial arithmetic. It is more general than the stated question because it's easy to decompose a polynomial with listed terms into a circuit --- the only hard part is exponents in binary and you can do that by squaring up --- and composition of polynomials can be implemented in a straight-line program by the definition of a straight-line program.

The complexity class BPP means yes-no questions answered in polynomial time by a randomized algorithm which gives a probably-correct answer, with probability $p > c > 1/2$. The complexity class RP is the same thing, except that if the program answer yes, it is certainly correct; if it answers no, it is only probably correct. The probability of correctness can be amplified to very close to 1. It is a well-known conjecture that BPP = P, and obviously BPP contains RP and RP contains P. The basis of the conjecture is that good pseudo-random number generators seem to exist. However, there are strong theoretical reasons that even RP = P is a very hard conjecture.

Ibarra and Moran give a polynomial-time algorithm in RP to show that an arithmetic circuit over $\mathbb{Q}$ (say) is non-zero. (So there is an algorithm in co-RP that the circuit is zero -- this is just switching "yes" and "no".) The algorithm consists of plugging in large values at random. It is a bit easier to see what they do over $\mathbb{Z}$, and not really different because you can reduce $\mathbb{Q}$ to $\mathbb{Z}$ by decomposing fractions into numerators and denominators. They make an exponentially large box in $\mathbb{Z}^n$, and they show that if the circuit is non-zero, then it is usually non-zero in the box, using simple (but skillful) counting estimates for zero values.

Kabanetz and Impagliazzo show that some of the same strong theoretical difficulties that obstruct the conjecture that BPP = P or RP = P, also make it hard to test circuit equality in P. So you should recognize Ibarra-Moran as efficient in practice because it is in co-RP, believe that Ibarra-Moran can be converted to P using pseudo-random numbers, and be satisfied that no one can provably find any algorithm for the problem in P.

$\endgroup$
1
  • $\begingroup$ @Mark The one caveat is that the negative Kabanetz-Impagliazzo theorem does not necessarily apply to your restricted situation. $\endgroup$ Nov 10, 2011 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.