Realizable Circuit Complexity: Embedding Computation in Space-Time

Classical circuit complexity characterizes parallel computation in purely combinatorial terms, ignoring the physical constraints that govern real hardware. The standard classes NC, AC, and TC treat unlimited fan-in, free interconnection, and polynomial gate counts as feasible -- assumptions that conflict with geometric, energetic, and thermodynamic realities. We introduce the family of realizable circuit classes RCd, which model computation embedded in physical d-dimensional space. Each circuit in RCd obeys conservative realizability laws: volume scales as O(td), cross-boundary information flux is bounded by O(td-1) per unit time, and growth occurs through local, physically constructible edits. These bounds apply to all causal systems, classical or quantum. Within this framework, we show that algorithms with runtime ω(nd/(d-1)) cannot scale to inputs of maximal entropy, and that any d-dimensional parallel implementation offers at most a polynomial speed-up of degree (d-1) over its optimal sequential counterpart. In the limit d→∞, RC_∞(polylog)=NC, recovering classical parallelism as a non-physical idealization. By unifying geometry, causality, and information flow, RCd extends circuit complexity into the physical domain, revealing universal scaling laws for computation.