A Polynomial-Time Algorithm for Maximum Clique: Establishing P = NP Through Reductions, Handlers, and Width Potentials

This work presents a deterministic polynomial-time algorithm for the Maximum Clique problem, establishing that P equals NP. The solver unifies four verified mechanisms: (1) correctness-preserving reductions and contractions, (2) certified tie-handlers and symmetry resolvers for highly regular graphs, (3) canonical signatures with cache soundness to avoid revisiting isomorphic states, and (4) a global width potential, called Theta-prime, that decreases under every solver move. The Master Width Theorem (MW-1) bounds the number of canonical signatures per potential triple by a polynomial in n, ensuring overall polynomial runtime. Correctness is maintained through the One-Clique Principle, certified deletions, and invariant preservation. Symmetry handlers guarantee solver progress and return exact clique values in structured graph families. The framework yields polynomial-time algorithms for Independent Set, Vertex Cover, SAT, and Graph Isomorphism, implying the collapse of the polynomial hierarchy and derandomization of BPP. Broader implications extend to cryptography, combinatorial optimization, and automated reasoning. The MW-1 system therefore provides a constructive, verifiable, and unified proof that P equals NP through deterministic canonical descent on structured search spaces.