Circuit Complexity

In Circuit Complexity, circuits are considered as calculation models. This results in different measures for the resource requirement than in classical complexity theory. We are particularly interested in the connection of certain circuit classes, first-level logic classes and algebra.

Circuits are modeled as directed, acyclic graphs, where the gates are labeled with Boolean functions. A circuit has a fixed number of inputs and outputs. So to be able to recognize languages, you have to proceed to consider families of circuits. In the case of circuits, the number of gates, the depth and the types of gates used are typically considered as resources.