preprint · Zenodo (CERN European Organization for Nuclear Research) · 2025

Graph-Based Deterministic Polynomial Algorithm for NP Problems

Lee, Changryeol

Cited by 0Open access

Abstract

The P vs NP problem asks whether every problem whose solution can be verified in polynomialtime (NP) can also be solved in polynomial time (P). In this paper, we present a proof that P =NP, demonstrating that every NP problem can be solved deterministically in polynomial time usinga graph-based algorithm. We introduce a new Computation Model that enables the simulation ofa Turing machine, and show that NP problems can be simulated efficiently within this framework.By introducing the concept of a Feasible Graph, we ensure that the simulation can be performedin polynomial time, providing a direct path to resolving the P = NP question. Our result hassignificant implications for fields such as cryptography, optimization, and artificial intelligence, whereNP-complete problems play a central role.

Cite this paper

APA 7

Lee, C. (2025). Graph-Based Deterministic Polynomial Algorithm for NP Problems. Zenodo (CERN European Organization for Nuclear Research). https://doi.org/10.5281/zenodo.17784110

MLA 9

Lee, Changryeol. “Graph-Based Deterministic Polynomial Algorithm for NP Problems.” Zenodo (CERN European Organization for Nuclear Research), 2025, https://doi.org/10.5281/zenodo.17784110.

Chicago

Lee, Changryeol. 2025. “Graph-Based Deterministic Polynomial Algorithm for NP Problems.” Zenodo (CERN European Organization for Nuclear Research). https://doi.org/10.5281/zenodo.17784110.

Harvard

Lee, C. (2025) ‘Graph-Based Deterministic Polynomial Algorithm for NP Problems’, Zenodo (CERN European Organization for Nuclear Research). Available at: https://doi.org/10.5281/zenodo.17784110.

BibTeX

@misc{lee2025graph,
  title = {{Graph-Based Deterministic Polynomial Algorithm for NP Problems}},
  author = {Lee, Changryeol},
  journal = {Zenodo (CERN European Organization for Nuclear Research)},
  year = {2025},
  doi = {10.5281/zenodo.17784110}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.