Bounded Exposure, Effective Witnesses, and the Structural Limits of Polynomial-Time Computation

Read full text
Authors: Michael Arias
Cited by: 0

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