On the Structural Impossibility of Local Constructions for Global Semantic Irreducibility
Abstract
This paper investigates whether globally irreducible dependencies, which are necessary for separating P from NP under structural frameworks based on computational invariance, can arise from locally specified constraint systems. Building on earlier work that reduced P versus NP to the existence of DGNL, it introduces the Global Semantic Entanglement Index as a quantitative measure of irreducibility. Through theoretical analysis and systematic experimentation, it shows that broad classes of constructions—including EXACTLY-ONE gadgets, Tseitin systems, and monotone irreversible constraints—collapse to constant entanglement. A meta-theorem proves that local reversibility and semantic monotonicity prevent global irreducibility. The results sharply delimit the remaining search space for P versus NP separations.
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