Realizable Circuit Complexity: Embedding Computation in Space-Time

Benjamin Prada, Ankur Mali

Classical circuit complexity characterizes parallel computation in purely combinatorial terms, ignoring the physical constraints that govern real hardware. The standard classes $\m…