Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Circuit complexity
Summary
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 C_{1},C_{2},\ldots (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 \mathsf{NP}\not\subseteq \mathsf{P/poly} would separate P and NP (see below).
Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly.
Size and depth
A Boolean circuit with n input bits is a directed acyclic graph in which every node (usually called gates in this conte
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications
Loading
Related people
Loading
Related units
Loading
Related concepts
Loading
Related courses
Loading
Related lectures
Loading