Arithmetic circuit complexity

In computational complexity theory, arithmetic circuits are the standard model for computing polynomials. Informally, an arithmetic circuit takes as inputs either variables or numbers, and is allowed to either add or multiply two expressions it has already computed. Arithmetic circuits provide a formal way to understand the complexity of computing polynomials. The basic type of question in this line of research is "what is the most efficient way to compute a given polynomial

f

{\displaystyle f}

?"

Definitions

An arithmetic circuit

C

{\displaystyle C}

over the field

F

{\displaystyle F}

and the set of variables

x

1

,

…

,

x

n

{\displaystyle x_{1},\ldots ,x_{n}}

is a directed acyclic graph as follows. Every node in it with indegree zero is called an input gate and is labeled by either a variable

x

i

{\displaystyle x_{i}}

or a field element in

F

.

{\displaystyle F.}

Every other gate is labeled by either

+

{\displaystyle +}

or

×

;

{\displaystyle \times ;}

in the first case it is a sum gate and in the second a product gate. An arithmetic formula is a circuit in which every gate has outdegree one (and so the underlying graph is a directed tree).

A circuit has two complexity measures associated with it: size and depth. The size of a circuit is the number of gates in it, and the depth of a circuit is the length of the longest directed path in it. For example, the circuit in the figure has size six and depth two.