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

Graph-Based Deterministic Polynomial Algorithm for NP Problems

Lee, Changryeol

Cited by 0Open access

Abstract

The P versus NP problem asks whether every language verifiable in polynomial time can also be decided in deterministic polynomial time. In this paper, we present a constructive proof that P = NP via a deterministic polynomial-time algorithm based on a graph-based computation framework.We introduce a model where edges correspond to deterministic Turing machine transitions. Because these execution steps formpaths sharing the initial edge, the total number of edges is polynomially bounded due to overlapping edges across the entire certificate space. By shifting the verification focus from searching over exponential certificates to incremental edge extensions through verification of their validity, we reduce the complexity of the verification process to polynomial size.A key feature of our approach is that each extension step enforces global consistency via a local in-feasibility trimmingtool. This mechanism systematically preserves consistent NP paths to the edge under verification, ensuring the graph remains globally feasible at every stage without explicit enumeration of certificates. Both extension and trimming steps are strictly bounded by a polynomial in the input size. Consequently, our construction decides NP problems in deterministic polynomial time, providing a direct resolution to the P versus NP question.

Cite this paper

APA 7

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

MLA 9

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

Chicago

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

Harvard

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

BibTeX

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

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