Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework

Authors: Changryeol Lee

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 a polynomial-time NP verifier simulation framework. We show that both machines operate in polynomial time and, for satisfiable instances, deterministically generate valid witnesses, thereby extending the framework to deterministic FNP computation without increasing the degree of polynomial complexity. Furthermore, we provide a complete implementation of the framework, including the dynamic computation graph, feasible-graph construction, verification walks, and Turing-machine simulation via edge extensions. The implementation behaves in accordance with the predicted polynomial-time bounds. To ensure transparency and reproducibility, the complete Python implementation and source code are made available in a public online repository.