Graph-Based Deterministic Polynomial Framwork for NP Problems
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918422241083392 |
|---|---|
| author | Lee, Changryeol |
| author_facet | Lee, Changryeol |
| contents | 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 by introducing a universal, graph-based deterministic framework applicable to all NP problems without requiring reduction to an NP-complete problem. We model computational transitions as edges within a unified graph structure, where edges correspond to the steps of a deterministic verifier Turing machine for all possible certificates. Due to the overlap of edges among computation paths, the total cardinality of the edge set remains polynomially bounded. A key feature of our approach is that each extension step enforces global consistency via a local infeasibility trimming tool. This mechanism systematically preserves valid NP paths that lead to the target edge under polynomial verification, ensuring the graph remains globally feasible at every stage without explicit enumeration. This represents a paradigm shift from searching over exponential certificates to the incremental extension of verified edges. Since our construction decides NP problems in deterministic polynomial time, it provides a direct resolution to the P versus NP question. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13166 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph-Based Deterministic Polynomial Framwork for NP Problems Lee, Changryeol Computational Complexity F.1.3; F.2.0 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 by introducing a universal, graph-based deterministic framework applicable to all NP problems without requiring reduction to an NP-complete problem. We model computational transitions as edges within a unified graph structure, where edges correspond to the steps of a deterministic verifier Turing machine for all possible certificates. Due to the overlap of edges among computation paths, the total cardinality of the edge set remains polynomially bounded. A key feature of our approach is that each extension step enforces global consistency via a local infeasibility trimming tool. This mechanism systematically preserves valid NP paths that lead to the target edge under polynomial verification, ensuring the graph remains globally feasible at every stage without explicit enumeration. This represents a paradigm shift from searching over exponential certificates to the incremental extension of verified edges. Since our construction decides NP problems in deterministic polynomial time, it provides a direct resolution to the P versus NP question. |
| title | Graph-Based Deterministic Polynomial Framwork for NP Problems |
| topic | Computational Complexity F.1.3; F.2.0 |
| url | https://arxiv.org/abs/2508.13166 |