Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.08471
curl -X POST /api/v1/records/arxiv/2603.08471/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.08471/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'