Bounded Exposure, Effective Witnesses, and the Structural Limits of Polynomial-Time Computation
Abstract
This paper develops a structural framework for polynomial-time computation based on bounded exposure and effective incompatibility witnesses. Building on earlier results that ruled out non-adaptive algorithms and linked NP-hardness to global irreducible dependencies, it proves that every deterministic polynomial-time computation admits a bounded exposure normal form and introduces the Strong Bounded Exposure with Effective Witnesses principle. This principle asserts that rejection must be accompanied by a finite, local, and extractable certificate. Through systematic attempts to refute this hypothesis across combinatorial, algebraic, spectral, and statistical paradigms, the paper finds no counterexamples. The framework reduces the P versus NP problem to whether NP-complete problems admit globally irreducible dependencies that evade all effective witnesses.
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