✳flâneur — a map of the web's best reading

Circuit complexity - Wikipedia

en.wikipedia.org · 3,348 words · saved by 1 readers

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 𝐶 1 , 𝐶 2 , … (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. A Boolean circuit with 𝑛 input bits is a directed acyclic graph in which every node (usually called gates in this context) is either an input node of in-degree 0 labelled by one of the 𝑛 input bit

Circuit complexity - Wikipedia Jump to content From Wikipedia, the free encyclopedia Model of computational complexity Example Boolean circuit. The ∧ {\displaystyle \wedge } nodes are AND gates , the ∨ {\displaystyle \vee } nodes are OR gates , and the ¬ {\displaystyle \neg } nodes are NOT gates . 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

Explore this link on the map →

related reading