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.

  • $\begingroup$ What do you mean by equivalence exactly? Do you want to test whether the functions computed by the two circuits are the same? $\endgroup$
    – Bruno
    Apr 4, 2014 at 12:28
  • $\begingroup$ Does your class of circuits fit into the framework for polynomial identity testing? $\endgroup$ Apr 4, 2014 at 12:30
  • $\begingroup$ 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. $\endgroup$
    – Bruno
    Apr 4, 2014 at 12:33
  • 2
    $\begingroup$ I think this paper is related: Deterministically testing sparse polynomial identities of unbounded degree. Another question: Are you interested in deterministic or randomized algorithms? $\endgroup$
    – Bruno
    Apr 4, 2014 at 15:16
  • 1
    $\begingroup$ If you're unsure, you should start with the randomized versions, since they are generally much, much simpler. $\endgroup$ Apr 4, 2014 at 16:22


Your Answer

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