Arithmetic circuit complexity
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 ?"
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 ?" We would also like to mention the best circuit known for the permanent of an n \times n matrix. As for the determinant, the naive circuit for the permanent has size roughly n!. However, for the permanent the best circuit known has size roughly 2^n, which is given by Ryser's formula: for an n \times n matrix X = (x_{i,j}), \operatorname{perm}(X)=(-1)^n\sum_{S \subseteq \{1,\ldots,n\}}(-1)^ \prod_{i=1}^n \sum_{j \in S} x_{i,j} (this is a depth three circuit).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1377677265 under CC BY-SA 4.0; modifications have been made.