Arithmetic circuits complexity

Arithmetic circuits are circuits whose gates compute operations over a semi-ring instead of the usual Boolean connectives. The theory of arithmetic circuits, a very rich field with strong upper and lower bounds on the complexity of practical computational problems, serves as a theoretical base for computer algebra and algebraic computations in symbolic computation software packages.

Computation model

Let $R=(R,+,\times ,0,1)$ be a semi-ring. A function over $R$ IS A FUNCTION $f:R^{m}\rightarrow R$ for some $m\in \mathbb {N}$. Here $m$ is called the arity of $f$. A family of functions over $R$ is a sequence $f=(f^{n})_{n\in \mathbb {N} }$, where $f^{n}$ is a function over $R$ of artiy $n$.

Reference

• Vollmer, Heribert (1999), Introduction to Circuit Complexity - A Uniform Approach.