Irreducible Global Dependencies, Structural Exposure, and a Conditional Separation Framework for P versus NP

Read full text
Authors: Michael Arias
Cited by: 0

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