{"id":"arxiv/2603.08471","url":"https://arxiv.org/abs/2603.08471","tags":["math.OC","cs.CC","cs.IT"],"score":0,"title":"Intrinsic Sequentiality in P: Causal Limits of Parallel Computation","domain":"math.OC","source":"arxiv","authors":["Jing-Yuan Wei"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-09","reactions":{}}