This concept treats classical computation through the circuit model: any function from n input bits to m output bits reduces to evaluating m Boolean functions, each of which can be constructed as a directed acyclic circuit of gates drawn from a universal set (AND, OR, NOT, plus input of variables and constants), with the disjunctive normal form giving a canonical decomposition. It belongs to the theory of computation and computational complexity, presented as the classical foundation from which quantum computation departs, and it formalizes problem hardness by how circuit size scales with input length. Central results include a counting argument showing most Boolean functions require exponential-size circuits, and the definitions of the complexity classes P, NP, co-NP, NP-completeness, and reducibility.
This concept treats classical computation through the circuit model: any function from n input bits to m output bits reduces to evaluating m Boolean functions, each of which can be constructed as a d…