A directed acyclic network of Boolean logic gates (AND, OR, NOT, etc.) connected by wires that computes Boolean functions from input bits to output bits; used as a nonuniform model of computation where each input size has its own circuit.

Principle

Compute a Boolean function by composing small, fixed logical primitives in an acyclic graph so that outputs are deterministic Boolean combinations of inputs; complexity is measured by size (number of gates) and depth (longest path).

Demonstration

For a fixed input length n, design a circuit that computes parity by XORing input bits pairwise in a balanced binary tree of XOR gates; analyze depth as O(log n) and size as O(n).

Misapplication

Treating a single circuit as a uniform algorithmic description for all input sizes without specifying a circuit family or assuming arbitrary fan-in/fan-out without cost, leading to misleading complexity claims.

Consequence

Provides a concrete, size-and-depth-based model for nonuniform complexity classes (e.g., P/poly) and hardware realizability insights; depth relates to parallel time while size relates to resource cost.

Reversal

A sequential, uniform model like the Turing machine or RAM describes a single algorithmic procedure that works for all input sizes via a finite program, inverting the per-size nonuniform circuit viewpoint.

Boundary

Assumes boolean logic and acyclicity; excludes sequential circuits with memory unless augmented with registers; cost models vary on gate fan-in, fan-out, and gate types; does not capture probabilistic or quantum gates unless explicitly extended.

Semantic Tension

Close to formulas (tree-shaped circuits) and branching programs; tension arises between circuit families (nonuniform) and uniform algorithmic models where a single description must scale with input length.

Synthesis

A static, acyclic composition of Boolean gates parameterized by input size that maps input bits deterministically to outputs; measuring size and depth yields insights into nonuniform and parallel computational resources.