The Globality Theorem: An Information-Theoretic Lower Bound for Distributed Constraint Resolution

This work introduces and proves the Globality Theorem, an information-theoretic lower bound on the resolution of distributed constraint satisfaction problems. We show that for a broad family of locally consistent constraint systems with nnn variables and kkk regions, any protocol that correctly decides global satisfiability with constant error must generate Ω(n)\Omega(n)Ω(n) bits of irreducible global information (and Ω(n/k2)\Omega(n/k^2)Ω(n/k2) in general). This information is measured using multi-information (total correlation), capturing genuinely higher-order correlations that cannot be detected by pairwise mutual information alone. The result is established via: An explicit reduction from the multi-party Set Disjointness (DISJ) problem to locally consistent constraint systems. A conversion of known information complexity lower bounds for DISJ into lower bounds on transcript-conditioned multi-information. A demonstration that deciding global satisfiability necessarily requires generating correlations absent from the initial, independent local inputs. Conceptually, the theorem shows that global inconsistency is an informationally non-local property: it cannot be detected or certified by purely local reasoning without the creation of global correlations. This provides an information-theoretic explanation for the intrinsic difficulty of resolving global properties in distributed constraint systems. The paper also discusses physical interpretations of this informational cost, including a space–time trade-off for physical implementations and a connection with Landauer’s principle, linking the generation of information to unavoidable thermodynamic costs. Overall, the Globality Theorem characterizes a fundamental informational bottleneck separating local consistency from global satisfiability, with implications for communication complexity, distributed algorithms, constraint satisfaction, and the physical limits of computation.