# Complexity of equivalence testing of arithmetic circuits

I have a very specific problem that appears to be close to equivalence testing for arithmetic circuits (checking whether the computed functions are the same).

Since I'm completely new to the field, I'm asking for some references, hopefully as close as possible to my concrete problem.

I want to find out the complexity of comparing two arithmetic circuits (directed graphs with addition and multiplication nodes). My concrete problem has the following particularities.

• There is only one input variable. Thus the circuits encode a function $\mathbb{N} \to \mathbb{N}$. Are there any results about a constant number of input variables?
• There might appear leafs of the form $c^n$ with $n$ being the input variable and $c \in \mathbb{N}$ some constant.

I'm happy with both surveys or original works about such equivalence problems. Books are also ok, but I prefer material that's downloadable.

• What do you mean by equivalence exactly? Do you want to test whether the functions computed by the two circuits are the same? Apr 4, 2014 at 12:28
• Does your class of circuits fit into the framework for polynomial identity testing? Apr 4, 2014 at 12:30
• Suppose there is no $c^n$ input, so that the function represented by a circuit is a polynomial. Do you have an a priori bound on the degree of this polynomial? Because you can test equality in time polynomial in this degree (say $d$), by testing equality on $(d+1)$ input values. Apr 4, 2014 at 12:33
• I think this paper is related: Deterministically testing sparse polynomial identities of unbounded degree. Another question: Are you interested in deterministic or randomized algorithms? Apr 4, 2014 at 15:16
• If you're unsure, you should start with the randomized versions, since they are generally much, much simpler. Apr 4, 2014 at 16:22