Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly.
- B
- 2
- Comment
- enIn theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly.
- Cs1Dates
- eny
- Date
- enMay 2019
- Depiction
- Group
- en"nb"
- Has abstract
- enIn theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that would separate P and NP (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly.
- Is primary topic of
- Circuit complexity
- Label
- enCircuit complexity
- Link from a Wikipage to an external page
- eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/
- www.cs.tau.ac.il/~zwick/scribe-boolean.html
- Link from a Wikipage to another Wikipage
- Abstract machine
- AC (complexity)
- AC0
- ACC0
- Alexander Razborov
- AND gate
- Average-case complexity
- B. G. Teubner Verlag
- Bit
- Boolean circuit
- Boolean function
- Category:Circuit complexity
- Category:Computational complexity theory
- Circuit minimization
- Claude Shannon
- Clique problem
- Complexity class
- Computational complexity theory
- Computational problem
- Computational resource
- Derandomization
- Deterministic Turing machine
- Directed acyclic graph
- DLOGTIME
- Electronic Colloquium on Computational Complexity
- File:Three input Boolean circuit.jpg
- Formal language
- In-degree
- Johan Håstad
- John Wiley & Sons Ltd.
- MA (complexity)
- Machine that always halts
- Natural proof
- NC (complexity)
- NC1 (complexity)
- NOT gate
- NP (complexity)
- OR gate
- P (complexity)
- Parity function
- Pierre McKenzie
- poly
- PP (complexity)
- Ran Raz
- Recursive language
- Ryan Williams (computer scientist)
- S2P (complexity)
- Springer Verlag
- TC0
- Theoretical computer science
- Turing machine
- Turing machine equivalents
- P
- enP
- SameAs
- 8CcA
- Complessità dei circuiti
- Complexidade de circuitos
- Complexitat de circuits
- m.0267lqh
- Q1055112
- 回路計算量
- 电路复杂性
- Subject
- Category:Circuit complexity
- Category:Computational complexity theory
- Thumbnail
- WasDerivedFrom
- Circuit complexity?oldid=1086836071&ns=0
- WikiPageLength
- 20342
- Wikipage page ID
- 7641969
- Wikipage revision ID
- 1086836071
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite web
- Template:Reflist
- Template:Short description
- Template:Su
- Template:Use dmy dates
