Globality Requirements for Polynomial-Time Algorithms in NP: A Formal Taxonomy of Non-Local Inference Mechanisms

Globality Requirements for Polynomial-Time Algorithms in NP introduces a formal, information-theoretic framework for analyzing why existing algorithms systematically fail to solve NP-complete problems in polynomial time in the worst case. The paper defines the notion of globality capacity (Γ) as the maximum reduction of entropy in the witness space that an inference operation can achieve in a single step. This quantity is interpreted as the inferential bandwidth of an algorithm and provides a rigorous distinction between local reasoning and genuinely global inference mechanisms. Using this framework, the article develops a taxonomy of global computational principles—including information accumulation, structural decomposition, continuous relaxations, randomized exploration, quantum inference, external computational resources, and learning-based methods—and establishes explicit upper bounds on their globality capacity. It is shown that all known algorithmic paradigms for NP, including modern SAT solvers, parameterized algorithms, convex relaxations, probabilistic methods, quantum algorithms, and neural approaches, fall strictly below the linear globality capacity required for exact polynomial-time performance in the worst case. The work thereby formalizes a structural locality barrier, complementary to classical barriers such as relativization and natural proofs, and proposes a necessary condition for any polynomial-time algorithm for NP-complete problems: the existence of at least one inference operation with super-constant globality capacity. While the paper does not resolve the P vs NP question, it provides a precise mathematical benchmark for evaluating future paradigms and clearly delineates the kind of non-local inference that would be required to overcome current limitations.