Irreducible Global Dependencies, Structural Exposure, and a Conditional Separation Framework for P versus NP
Abstract
This paper develops a structural framework for the P versus NP problem based on irreducible global dependencies in constraint satisfaction problems. Building on earlier work characterizing polynomial-time computation by semantic confluence and local certifiability, it introduces a quantitative notion of global non-local dependency using localization radius in compatibility complexes. Explicit NP-complete SAT formulas are constructed by amplifying EXACTLY-ONE surface constraints, yielding superpolynomial families of independent global cycles. A minimal structural exposure axiom (M2) is isolated, asserting that deterministic polynomial-time computation can only eliminate inconsistency through bounded local accumulation. Under this axiom, the constructed formulas separate P from NP. The framework reduces P versus NP to a sharply defined structural hypothesis about exposure in efficient computation.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Constraint Satisfaction and Optimization
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 4 February 2026
- Language
- EN
- Document type
- Preprint