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 Graph Search.
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 (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 bits, an AND gate, an OR gate, or a NOT gate. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its inputs. The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate.
There are two major notions of circuit complexity The circuit-size complexity of a Boolean function is the minimal size of any circuit computing . The circuit-depth complexity of a Boolean function is the minimal depth of any circuit computing .
These notions generalize when one considers the circuit complexity of any language that contains strings with different bit lengths, especially infinite formal languages. Boolean circuits, however, only allow a fixed number of input bits. Thus, no single Boolean circuit is capable of deciding such a language. To account for this possibility, one considers families of circuits where each accepts inputs of size . Each circuit family will naturally generate the language by circuit outputting when a length string is a member of the family, and otherwise.
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.
Ontological neighbourhood
Related courses (14)
CS-524: Computational complexity
In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation.
This course advances the students knowle
EE-280: Electronics
Présentation des principaux composants de base de l'électronique.
Analyse de circuits à base d'amplificateurs opérationnels.
Introduction aux circuits logiques élémentaires.
Principe de la conversion
EE-708: Advanced topics in electromagnetic compatibility
After a series of common introductory topics covering an introduction to electromagnetic compatibility, modeling techniques and selected chapters from EMC, each student will study a specific topic, wh
Related lectures (44)
Logic Systems: Representations and Arithmetic
Explores representations, arithmetic, and limitations in logic systems, including place-value notation and binary arithmetic.
Shor Algorithm: Circuit Details
Covers the details of the Shor algorithm circuit and its complexity.
Impedances and Admittances: Introduction to Complex Numbers
Introduces impedances and admittances, emphasizing the role of complex numbers in circuit theory.
Related publications (189)
Related people (32)
Related concepts (11)
Computational problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that are the nontrivial prime factors of n.
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as ∧, disjunction (or) denoted as ∨, and the negation (not) denoted as ¬.
Advice (complexity)
In computational complexity theory, an advice string is an extra input to a Turing machine that is allowed to depend on the length n of the input, but not on the input itself. A decision problem is in the complexity class P/f(n) if there is a polynomial time Turing machine M with the following property: for any n, there is an advice string A of length f(n) such that, for any input x of length n, the machine M correctly decides the problem on the input x, given x and A.