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

While prior work established a verifier-based polynomial-time framework for NP, explicit deterministicmachines for concrete NP-complete problems have remained elusive. In this paper, we construct fully specifieddeterministic Turing Machines (DTMs) for SAT and Subset-Sum within an improved NP verifier simulationframework. A key contribution of this work is the development of a functional implementation that bridgesthe gap between theoretical proofs and executable software. Our improved feasible-graph construction yieldsa theoretical reduction in the asymptotic polynomial degree, while enhanced edge extension mechanismssignificantly improve practical execution speed. We show that these machines generate valid witnesses, extendingthe framework to deterministic FNP computation without increasing complexity. The complete Pythonimplementation behaves in accordance with the predicted polynomial-time bounds, and the source code alongwith sample instances are available in a public online repository.