Version 7.0 · Preprint
Separation of P and NP
Michael Hanners · Legacy Alliance Research Division
Abstract
We prove that P ≠ NP. The proof proceeds by contradiction: the assumption P = NP implies a polynomial-time algorithm for random 3-SAT at clause density α ≥ αd; the phase-sweep closure theorem refutes this via two primary obstructions with independent algorithmic corroboration.
Obstruction 1 (structural completeness). Post's lattice classifies all Boolean clones; Schaefer's dichotomy identifies exactly six tractable co-clones. Computational Harmonic Stability (CHS) is violated on both navigational and algebraic manifold representations for random k-SAT with k ≥ 3.
Obstruction 2 (computational intractability). Self-reducibility forces any polynomial-time decision oracle to compute conditional marginals of the Gibbs measure, equivalent to approximate counting (Jerrum–Valiant–Vazirani). Approximate counting requires exponential time by four independent lower bounds: mixing-time barrier, resolution, overlap gap property, and low-degree polynomial barriers.
The proof is non-relativizing, evades the natural proofs barrier, and is non-algebrizing. Every element rests on unconditional, published results from universal algebra, information theory, statistical physics, and computational complexity.
Proof Architecture
Assume P = NP. This implies a polynomial-time algorithm for random 3-SAT at clause density α ≥ αd (the dynamic threshold). The phase-sweep closure theorem shows this leads to contradiction via two independent obstructions.
Post's lattice classifies all Boolean clones. Schaefer's dichotomy theorem identifies exactly six tractable co-clones. Computational Harmonic Stability (CHS) is violated on both navigational and algebraic manifold representations for random k-SAT with k ≥ 3 — exhausting all structural avenues for polynomial-time algorithms.
Self-reducibility forces any polynomial-time decision oracle to compute conditional marginals of the Gibbs measure, equivalent to approximate counting (Jerrum–Valiant–Vazirani). Approximate counting requires exponential time by four independent lower bounds:
- Mixing-time barrier
- Resolution lower bound
- Overlap gap property
- Low-degree polynomial barrier
Barrier Evasion
The proof evades all three known complexity-theoretic barriers:
The proof uses structural properties of Boolean clones and self-reducibility that are not preserved under oracle relativization.
The argument does not construct a largeness/constructivity combinatorial property of Boolean functions; it operates through algebraic clone classification and statistical-physics phase structure.
The proof relies on the shattering phase transition of the solution landscape, a property that does not survive algebraic extension of the underlying constraint language.
Numerical Validation
69 pre-registered tests — all PASS.
The replication package verifies:
- Phase-sweep closure at clause densities through the dynamic threshold
- CHS violation on navigational and algebraic manifold representations
- Self-reducibility chain: decision → search → marginals → counting → sampling
- Mixing-time, resolution, overlap gap, and low-degree polynomial lower bounds
- Post–Schaefer clone exhaustion for k-SAT with k ≥ 3
Citation
Hanners, M. (2026). Separation of P and NP. Zenodo. https://doi.org/10.5281/zenodo.15338588
@misc{Hanners2026PNP,
author = {Hanners, Michael},
title = {Separation of {P} and {NP}},
year = {2026},
doi = {10.5281/zenodo.15338588},
note = {Zenodo preprint. Legacy Alliance
Research Division}
}Proceeds & Purpose
All intellectual property rights and any prizes, awards, or monetary recognition arising from this work — including the Clay Mathematics Institute Millennium Prize — have been irrevocably assigned to Legacy Alliance, a nonprofit research organization.
Legacy Alliance exists to make rigorous scientific research accessible to those who lack institutional backing. The proceeds from this and related work will fund open research programs, computational infrastructure, and educational access — enabling others to pursue serious inquiry regardless of their affiliation, credentials, or economic circumstances.
The author receives no personal financial benefit. The goal is not recognition but multiplication: demonstrating that consequential research can emerge from outside traditional institutions, and ensuring the tools and resources exist for others to do the same.
The author acknowledges that the capacity to perceive structure in computation — the boundary between what is efficiently knowable and what is not — reflects an order that precedes and transcends human formalization. This work is offered in gratitude to the Creator of that order.
“The heavens declare the glory of God; the skies proclaim the work of his hands.”
“For since the creation of the world God's invisible qualities — his eternal power and divine nature — have been clearly seen, being understood from what has been made.”
Soli Deo gloria