将计算复杂度与物理空间结合，揭示真实硬件的计算极限。
Realizable Circuit Complexity: Embedding Computation in Space-Time
- 用物理维度建模电路，考虑体积与信息传输的现实约束。
- 证明高维并行计算最多只能多项式加速，且无法处理最大熵输入。
- 为经典与量子系统提供统一的物理计算理论框架，适合理论计算机学者。
经典电路复杂度仅从组合角度刻画并行计算，忽略真实硬件的物理限制。标准类NC、AC、TC假设无限扇入、自由互连和多项式门数可行，但违背几何、能量与热力学现实。本文提出可实现电路类RC_d，模拟嵌入d维空间中的计算。每个RC_d电路遵循保守可实现性定律：体积随时间呈O(t^d)增长，跨边界信息通量每单位时间不超过O(t^{d-1})，且增长依赖局部可构造的修改。这些约束适用于所有因果系统（经典或量子）。在该框架下，我们证明运行时间ω(n^{d/(d-1)})的算法无法扩展至最大熵输入；任意d维并行实现相对于最优串行版本最多提供度数为(d−1)的多项式加速。当d→∞时，RC_∞(polylog)=NC，恢复经典并行性作为非物理理想化。通过统一几何、因果性与信息流，RC_d将电路复杂度延伸至物理领域，揭示计算的普适尺度规律。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。