The Plus-One Theorem: Coordination as the Irreducible Bottleneck in Parallel Computation

We establish that for any computational problem requiring examination of m distinct possibilities, coordination cost is Ω(m) in all computational models that obey causal consistency; including abstract Turing machines when their operational structure is made explicit. We prove the Plus-One Theorem: even with m processors executing m tasks, an additional coordination layer must perform Ω(m) sequential work to enumerate, distribute, collect, and aggregate. This holds for both physical implementations (where thermodynamics enforces causality) and abstract models (where the axioms of computation themselves enforce it). The result demonstrates that P ≠ NP for all computational models where the existential quantifier must be operationally constructed rather than assumed as a primitive oracle. We address directly why standard Turing machine formalisms appear to evade this: they either assume nondeterminism as primitive (which is a specification language, not an operational model) or hide coordination costs in the transition function’s definition. When computation is analyzed as an operational process—even abstractly—the Plus-One constraint emerges as unavoidable.