Using the well-known (high school) method for computing
the determinant, it can be shown Detd can be computed by
poly(d)-sized arithmetic circuits. A very closely related family
of formal polynomials is the permanent:
Computing the permanent of a 0/1 matrix is not just NP-hard
but can in fact be used to count the number of satisfying
assignment for any Boolean formula, and count perfect
matching in a bipartite graph, and in some other problems
involving counting and estimation in statistics.
Although this family looks very similar to the determinant, it is widely believed that any arithmetic circuit computing Permd must be of size exponential in d. Showing that
the permanent cannot be computed by polynomial-size
arithmetic circuits is the biggest challenge in the field of
arithmetic circuit complexity.
1. 1. Importance of arithmetic circuits
To understand hardness of formal polynomial functions,
we first need to define a suitable measure of hardness.
Intuitively, a polynomial f = x1 . . . xn should be “easy” as this
is just a monomial. On the other hand, a polynomial such as
should also be “easy,”
despite having exponentially many monomials, as f ′ is not
much different from f. A measure of hardness, that is, robust
with respect to such minor transformations is provided by
arithmetic circuits. This model is particularly useful if we
would like to understand functions like the determinant
and permanent, which are very algebraic in nature. Valiant24
introduced two classes of formal polynomials as algebraic
analogs of the Boolean classes P and NP. Analogous to the
class P that consists of efficiently computable Boolean functions, the class VP is defined as the class of formal polynomials f (x1, . . . xn) with deg( f ) = poly(n) that can be computed
by arithmetic circuits of poly(n) size.
Analogous to the class NP that consists of Boolean
functions F(x1, . . ., xn) that can be expressed as
for some G ∈ P and m = poly(n), the class VNP consists of
formal polynomials f (x1, . . . , xn) that can be expressed as
for some formal polynomial g ∈ VP and m = poly(n).
Valiant24 showed that Detd and Permd are in some
sense complete for the classes VP and VNP, respectively.
Thus, showing that permanent cannot be computed by
polynomial-size arithmetic circuits would separate the algebraic analog of NP from the algebraic analog of P. Further,
if NP ⊄ P/poly, then it can be shown that VP ≠ VNP over
finite fields. Hence, proving VP ≠ VNP could be thought of
as a stepping stone toward proving P ≠ NP.
Another connection to the Boolean world is via the problem of polynomial identity testing (PIT), wherein we are given
an arithmetic circuit as input and are required to check if
the formal polynomial computed by the circuit is zero or
not. Although this algorithmic question has a very natural
randomized algorithm, constructing a deterministic algorithm would be major progress.
10 Further, as in the Boolean
world, derandomizing PIT has very deep connections to
proving arithmetic circuit lower bounds via hardness–
Thus understanding arithmetic circuits could be a first
step toward understanding Boolean circuits. Arithmetic circuits also have a lot of structure which, sometimes, have no
analogs in the Boolean world. The most important example of
this is the possibility of depth reduction for arithmetic circuits.
1. 2. The power of shallow circuits
Circuits with low depth correspond to computations which
are highly parallel, where edges indicate dependencies in
computation. Therefore it is natural to try to minimize the
depth of a circuit while allowing the size to increase somewhat. In the case of Boolean circuits, we know that very
shallow Boolean circuits are not powerful at all. It is known
that constant depth Boolean circuits consisting of ∧ and ∨
Figure 1. Examples of arithmetic circuits.
(x1 + x2)
2 (x1 + x2)
2 ( 1 + x1)( 1 + x2) . . . ( 1 + xn)
. . . 1
+ + + ...
x1 x2 x1 x1 x2 x2 xn