Arithmetic Circuit Value Problem (ArithCVP)

Input

An encoding $\overline{\alpha}$ of an arithmetic circuit $\alpha$ with dyadic operations $+$, $-$, and $\ast$, together with inputs $x_1, \ldots, x_n$ from a ring.

Problem

Does $\alpha$ on input $x_1, \ldots, x_n$ output 1?

Definitions

See CVP. An arithmetic circuit is a generalization of a circuit which allows doing more arbitrary operations on its inputs.

Status

$\P$-hard, but not known to be in $\P$ (Greenlaw, Hoover and Ruzzo [4]).

Remarks

The reduction to show hardness is from NANDCVP.

The problem is not necessarily in $\FP$ for infinite rings like $\Z$ or $\Q$, since intermediate values need not be of polynomial length. It will be in $\FP$ for any finite ring, and remains $\P$-hard in any ring. It is also $\P$-hard to decide whether all gates in an arithmetic circuit over $\Z$ have “small” values, say values of a magnitude $2^{n^{O(1)}}$. Cucker and Torrecillas [1] look at related problems. The problem is in $\NC$ for circuits of degree $2^{(\log n)^{O(1)}}$, where the degree of a vertex is one for inputs, and $d_1+d_2$ (respectively, $\max(d_1, d_2)$) when the vertex is a product (respectively, sum) of the values computed by two vertices of degree $d_1$ and $d_2$ (Miller, Ramachandran, and Kaltofen [2], Valiant et al. [3]).