A Rigorous Proof of P = NP

Abstract

This paper gives a rigorous proof of P = NP within the standard framework of computational complexity. The classical definitions of P and NP only require the running time of a solving algorithm to be polynomial, and impose no finite-time restriction on the process of searching for such an algorithm. By applying infinite-step traversal and probability limit theory, we prove that the deterministic polynomial-time algorithm corresponding to any NP problem can inevitably be found. Once the algorithm is obtained, the problem can be solved in polynomial time, which establishes P = NP.

Keywords