Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909000454373376 |
|---|---|
| author | Lee, Changryeol |
| author_facet | Lee, Changryeol |
| contents | While prior work established a verifier-based polynomial-time framework for NP, explicit deterministic machines for concrete NP-complete problems have remained elusive.
In this paper, we construct fully specified deterministic Turing Machines (DTMs) for SAT and Subset-Sum within an improved NP verifier simulation framework.
A key contribution of this work is the development of a functional implementation that bridges the gap between theoretical proofs and executable software.
Our improved feasible-graph construction yields a theoretical reduction in the asymptotic polynomial degree, while enhanced edge extension mechanisms significantly improve practical execution speed.
We show that these machines generate valid witnesses, extending the framework to deterministic FNP computation without increasing complexity.
The complete Python implementation behaves in accordance with the predicted polynomial-time bounds, and the source code along with sample instances are available in a public online repository. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10991 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework Lee, Changryeol Computational Complexity Formal Languages and Automata Theory F.1.1; F.2.2 While prior work established a verifier-based polynomial-time framework for NP, explicit deterministic machines for concrete NP-complete problems have remained elusive. In this paper, we construct fully specified deterministic Turing Machines (DTMs) for SAT and Subset-Sum within an improved NP verifier simulation framework. A key contribution of this work is the development of a functional implementation that bridges the gap between theoretical proofs and executable software. Our improved feasible-graph construction yields a theoretical reduction in the asymptotic polynomial degree, while enhanced edge extension mechanisms significantly improve practical execution speed. We show that these machines generate valid witnesses, extending the framework to deterministic FNP computation without increasing complexity. The complete Python implementation behaves in accordance with the predicted polynomial-time bounds, and the source code along with sample instances are available in a public online repository. |
| title | Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework |
| topic | Computational Complexity Formal Languages and Automata Theory F.1.1; F.2.2 |
| url | https://arxiv.org/abs/2602.10991 |