Data Structures and Algorithms

A Formal Proof of P ̸= NP: Self-Referential Complexity and Computational Limits

Authors: Javier Muñoz de la Cuesta
Comments: 19 Pages.

This article presents a formal proof that P ̸= NP, resolving one of the Clay Mathematics Institute’s Millennium Prize Problems. We introduce self-referential complexity, a measure of the computational cost when a deterministic algorithm verifies its own states. Applying this to the NP-complete Boolean SatisfiabilityProblem (SAT), we demonstrate that any deterministic algorithm requires a superpolynomial number of self-referential steps in the worst case, establishing an intrinsic barrier separating P from NP. The proof includes formal definitions, step-by-step mathematical derivations, examples, counterexamples, simulations, and verification conditions, with implications for complexity theory, cryptography, and the foundations of computation.
Category: Data Structures and Algorithms