Some problems in P require linear time even with unlimited parallelism — because causality cannot be parallelized.
A problem in P is solvable in polynomial time. Many problems in P are also highly parallelizable — they can be solved much faster with enough processors. The standard complexity framework (circuit depth, NC classes) characterizes which problems benefit from parallelism. But this framework abstracts away a physical constraint: information cannot travel faster than some fixed speed.
Wei (arXiv:2603.08471) proves via information-theoretic cut-set bounds and Fano's inequality that certain problems in P require Ω(N) time even with unbounded parallelism, provided the computation must respect causal structure — the constraint that a computation step can only use information from its causal past. The bound is not on circuit depth but on time in a spatially extended system where signals propagate at finite speed.
This separates two notions that standard complexity theory conflates: logical parallelizability (can the computation be rearranged into low depth?) and causal executability (can the computation run fast in a physical system?). A problem can be in NC (highly parallelizable in the logical sense) and still require linear time in any physical implementation that respects causality.
The floor is set by information flow. When the answer depends on data that is spatially distributed, and the dependence cannot be decomposed into independent subproblems, the time to collect and combine the information is bounded below by the spatial extent divided by the signal speed. No amount of parallelism helps — the bottleneck is not computation but communication.
Wei, "Intrinsic Sequentiality in P: Causal Limits of Parallel Computation," arXiv:2603.08471 (2026).