---
title: Arithmetic circuit complexity
slug: arithmetic-circuit-complexity
qid: 
snapshot: enwiki-001377677265
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1377677265
tags: [23603337, 26220375, 29176222]
---

# Arithmetic circuit complexity

> [!note] Provenance
> Snapshot `enwiki-001377677265` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1377677265> · Licensed CC BY-SA 4.0

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