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 already computed. Arithmetic circuits give us a formal way for understanding the complexity of computing polynomials. The basic type of question in this line of research is "what is the most efficient way for computing a given polynomial ${\displaystyle f}$?"

An arithmetic circuit ${\displaystyle C}$ over the field ${\displaystyle F}$ and the set of variables ${\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 ${\displaystyle x_{i}}$ or a field element in ${\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).

...
Wikipedia