Arithmetic circuit complexity on arvau

Wikipedia / Arithmetic circuit complexity

In computational complexity theory, arithmetic circuits are the standard model for computing polynomials?"

Definitions

An arithmetic circuit over the field is a directed acyclic graph as follows. Every node in it with indegree zero is called an input gate 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.

is a child

Overview

The answer to this question consists of two parts. The first part is finding some this part is usually called upper bounding The second part is showing that no other circuit can do better; this part is called lower bounding Although these two tasks are strongly related, proving lower bounds is usually harder, since in order to prove a lower bound one needs to argue about all circuits at the same time.

over the field of two elements this polynomial represents the zero function, but it is not the zero polynomial. This is one of the differences between the study of arithmetic circuits and the study of Boolean circuits. In Boolean complexity, one is mostly interested in computing a function, rather than some representation of it (in our case, a representation by a polynomial). This is one of the reasons that make Boolean complexity harder than arithmetic complexity. The study of arithmetic circuits may also be considered as one of the intermediate steps towards the study of the Boolean case, which we hardly understand.

Upper bounds

As part of the study of the complexity of computing polynomials, some clever circuits (alternatively algorithms) were found. A well-known example is Strassen's algorithm for matrix product matrices. This idea is the starting point of the best theoretical way for multiplying two matrices

Another interesting story lies behind the computation of the determinant

We would also like to mention the best circuit known for the permanent

(this is a depth three circuit).

Lower bounds

In fact, as in many areas of mathematics, counting arguments tell us that there are polynomials of polynomial degree that require circuits of superpolynomial size. However, these counting arguments usually do not improve our understanding of computation. The following problem is the main open problem in this area of research: find an explicit polynomial of polynomial degree that requires circuits of superpolynomial size.

given by Strassen and by Baur and Strassen. More precisely, Strassen used Bézout's theorem partial derivatives as well. This is one example where some upper bound helps in proving lower bounds; the construction of a circuit given by Baur and Strassen implies a lower bound for more general polynomials.

The lack of ability to prove lower bounds brings us to consider simpler models of computation. Some examples are: monotone circuits (in which all the field elements are nonnegative real numbers), constant depth circuits, and multilinear circuits (in which every gate computes a multilinear polynomial). These restricted models have been studied extensively and some understanding and results were obtained.

Algebraic P and NP

The most interesting open problem in computational complexity theory is the P vs. NP problem. Roughly, this problem is to determine whether a given problem can be solved as easily as it can be shown that a solution exists to the given problem. In his seminal work Valiant suggested an algebraic analog of this problem, the VP vs. VNP problem.

efficiently, with a polynomial size circuit.

One of the basic notions in complexity theory is the notion of completeness Valiant showed that the permanent is complete for the class VNP. So in order to show that VP is not equal to VNP, one needs to show that the permanent does not have polynomial size circuits. This remains an outstanding open problem.

Depth reduction

One benchmark in our understanding of the computation of polynomials is the work of Valiant, Skyum, Berkowitz and Rackoff. This result generalizes the circuit of Berkowitz to any polynomial of polynomial degree that has a polynomial size circuit (such as the determinant). The analog of this result in the Boolean setting is believed to be false.

This simulation is easier than the depth reduction of Valiant el al. and was shown earlier by Hyafil.