Present an algorithm to prove P = NP
收藏DataCite Commons2025-09-13 更新2026-02-09 收录
下载链接:
https://figshare.com/articles/dataset/Present_an_algorithm_to_prove_P_NP/30120814/1
下载链接
链接失效反馈官方服务:
资源简介:
Aiming to prove the P vs. NP problem, a long-standing challenge in computer science, we present a novel deterministic algorithm that solves the Hamiltonian path problem, a representative NP-complete problem, in polynomial time. The proposed "Rotation-Based Search Algorithm (RBSA)" uses a novel approach that transforms the topological structure of a graph into a 3D geometric problem. Each vertex is positioned as a point in 3D space via a quaternion, and this set of points is spatially transformed by systematic rotations and oscillations. By sorting the points in each transformed state in a specific coordinate order, we obtain Hamiltonian path candidates, which are then verified to satisfy the constraints of the actual graph.
The theoretical validity of this algorithm is supported by two key arguments. First, we demonstrated completeness by proving that if a path exists, there must exist a rotation state in three-dimensional space that perfectly aligns the path (path linearization). Second, we proved polynomial time complexity by proving that the minimum distance between critical rotation angles that change the sorting order of the algorithm cannot be smaller than $1/\text{poly}(n)$, due to the "root separation principle" of algebraic number theory. These proofs imply that the Hamiltonian path problem belongs to the set P.
In conclusion, the Hamiltonian path problem, an NP-complete problem, can be solved in polynomial time and thus belongs to P. This implies that the SAT problem, another NP-complete problem, also belongs to P. Therefore, this paper presents the final conclusion that P=NP.
提供机构:
figshare
创建时间:
2025-09-13



