On the Structural Impossibility of Local Constructions for Global Semantic Irreducibility

Read full text
Authors: Michael Arias
Cited by: 0

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