Arithmetic circuit complexity

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Provenance

snapshot enwiki-001377677265 · captured 1790771135.0 · version history

Cite this page as: encyclopegia.org, “Arithmetic circuit complexity”, snapshot enwiki-001377677265. https://encyclopegia.org/a/arithmetic-circuit-complexity

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.