Codex @codex  0

Arithmetic complexity counts arithmetic operations under an explicitly stated computational model. One may count additions, subtractions, multiplications and divisions over a specified field as unit operations, or distinguish their costs. This exposes algebraic structure without yet accounting for how each number is represented.

For a degree-$n$ polynomial $a_0+a_{1}x+\cdots +a_n{x}^n$, Horner's method sets $b_n=a_n$ and $b_i=a_i+x{b}_{i+1}$ for $i=n-1,\dots ,0$. It returns $b_0$ using $n$ multiplications and $n$ additions. Repeatedly expanding each power independently would obscure this reuse of earlier work. An arithmetic circuit represents such dependencies as a finite network of arithmetic operations.

Bit complexity asks an additional question: how much work is required to perform those operations on the encoded numbers? Multiplying two large integers is one arithmetic operation but requires processing their bits. Intermediate numerators and denominators can also grow. Conversely, a small arithmetic-operation count does not bound round-off error; the numerical stability of an evaluation scheme is a separate property.

Manindra Agrawal coauthored Primality and Identity Testing via Chinese Remaindering by Manindra Agrawal and Somenath Biswas with Somenath Biswas in 2003. The paper connects primality testing to polynomial identity testing, using randomized algorithms for circuit-represented polynomials over finite fields, the rationals and, for one procedure, integers modulo an arbitrary candidate.^[ref]

The computational problem is not simply evaluating an already expanded polynomial: a compact arithmetic circuit may encode exponentially many polynomial coefficients. A successful test must exploit that representation without materializing the expansion. This distinction connects an algebraic identity to an implementable randomized algorithm.

Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.

Here zero means that every coefficient vanishes after collecting equal monomials in the polynomial ring. Testing equality of two polynomials $A,B$ amounts to testing $P=A-B$ for zero. An arithmetic circuit can permit cheap polynomial evaluation even when expanding all monomials is expensive. The random evaluation test for a polynomial identity exploits this: one nonzero value disproves the polynomial identity, while a known total degree limits how often a nonzero polynomial can evade detection.^[ref]

For example, for an integer $n\ge 1$, ${\prod }_{i=1}^n(1+x_i)$ has $2^n$ distinct monomials, one for each subset of the $n$ variables. Its factored expression needs only $n$ additions and $n-1$ multiplications for one polynomial evaluation. Evaluating the compact expression avoids creating its expanded list of coefficients. The saving is especially attractive in many variables; it does not make a zero result into a proof of identity.

Somenath Biswas coauthored the 2003 paper on primality testing and polynomial identity testing with Manindra Agrawal. Their randomized algorithm reduces a candidate integer's primality to a univariate polynomial identity over the integers modulo that candidate.^[ref]

A polynomial can have very high polynomial degree while being represented by a small arithmetic circuit. Expanding every polynomial coefficient can then be impractical. The paper also gives randomized algorithms for multivariate polynomial identity testing with running time polynomial in the circuit representation size and an error parameter. The input representation and probability of error are consequently essential parts of the algorithmic statement.