{"ID":2867237,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.19161","arxiv_id":"2509.19161","title":"Realizable Circuit Complexity: Embedding Computation in Space-Time","abstract":"Classical circuit complexity characterizes parallel computation in purely combinatorial terms, ignoring the physical constraints that govern real hardware. The standard classes $\\mathbf{NC}$, $\\mathbf{AC}$, and $\\mathbf{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 $\\mathbf{RC}_d$, which model computation embedded in physical $d$-dimensional space. Each circuit in $\\mathbf{RC}_d$ obeys conservative realizability laws: volume scales as $\\mathcal{O}(t^d)$, cross-boundary information flux is bounded by $\\mathcal{O}(t^{d-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 $ω(n^{d/(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\\to\\infty$, $\\mathbf{RC}_\\infty(\\mathrm{polylog})=\\mathbf{NC}$, recovering classical parallelism as a non-physical idealization. By unifying geometry, causality, and information flow, $\\mathbf{RC}_d$ extends circuit complexity into the physical domain, revealing universal scaling laws for computation.","short_abstract":"Classical circuit complexity characterizes parallel computation in purely combinatorial terms, ignoring the physical constraints that govern real hardware. The standard classes $\\mathbf{NC}$, $\\mathbf{AC}$, and $\\mathbf{TC}$ treat unlimited fan-in, free interconnection, and polynomial gate counts as feasible -- assumpt...","url_abs":"https://arxiv.org/abs/2509.19161","url_pdf":"https://arxiv.org/pdf/2509.19161v3","authors":"[\"Benjamin Prada\",\"Ankur Mali\"]","published":"2025-09-23T15:40:36Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.LG\"]","methods":"[]","has_code":false}