Global Dependence, Reductions, and Semantic Fragmentation in NP-Complete Problems

Read full text
Authors: Michael Arias
Cited by: 0

Abstract

This paper analyzes whether irreducible global dependence is a robust structural property of NP-complete problems. Building on prior work showing that deterministic polynomial-time computation is causally and filtrationally constrained, it studies how candidate invariants of global dependence behave under polynomial-time reductions. It proves that geometric and topological formulations are unstable and introduces a semantic invariant based on Helly-type properties of extension spaces. While this invariant is preserved under locality-respecting reductions such as Cook–Levin, it is shown to collapse under general reductions due to information compression. These results explain structural obstacles faced by global-structure approaches to P vs NP and identify precise conditions under which such approaches may remain viable.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Computability Logic AI Algorithms

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
4 February 2026
Language
EN
Document type
Preprint