{
  "id": "enwiki-001377677265",
  "slug": "arithmetic-circuit-complexity",
  "title": "Arithmetic circuit complexity",
  "qid": "",
  "lead": "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 ?\"",
  "body": "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).",
  "categories": [
    "23603337",
    "26220375",
    "29176222"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1377677265",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1790771135.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001377677265",
    "type": "webpage",
    "title": "Arithmetic circuit complexity",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/arithmetic-circuit-complexity",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001377677265",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1377677265",
    "note": "Immutable snapshot enwiki-001377677265"
  }
}