Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
This work addresses the fundamental limits of parallel computation for researchers in complexity theory, showing that certain problems have intrinsic sequentiality, which is incremental in highlighting causal structure gaps.
The paper tackles the problem of identifying polynomial-time decision problems that inherently require sequential execution, proving that a specific class of problems with causal constraints cannot be parallelized and must take at least Ω(N) time, ruling out asymptotic speedup.
We study a polynomial-time decision problem in which each input encodes a depth-$N$ causal execution in which a single non-duplicable token must traverse an ordered sequence of steps, revealing at most $O(1)$ bits of routing information at each step. The uncertainty in the problem lies in identifying the delivery path through the relay network rather than in the final accept/reject outcome, which is defined solely by completion of the prescribed execution. A deterministic Turing machine executes the process in $Î(N)$ time. Using information-theoretic tools - specifically cut-set bounds for relay channels and Fano's inequality - we prove that any execution respecting the causal constraints requires $Ω(N)$ units of causal time, thereby ruling out asymptotic parallel speedup. We further show that no classical $\mathbf{NC}$ circuit family can implement the process when circuit depth is interpreted as realizable parallel time. This identifies a class of polynomial-time problems with intrinsic causal structure and highlights a gap between logical parallelism and causal executability.