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

Jul 16, 2026

Upload by Himbo

Previous work provided a verifier-based polynomial-time simulation framework for NP, but it did not deliver explicit deterministic Turing machines for concrete NP-complete problems. This paper constructs fully specified deterministic certificate-oblivious verifier machines for SAT and Subset-Sum within an improved NP verifier simulation framework. Key advances include a refined feasible-graph construction that reduces the asymptotic polynomial degree and faster practical execution via enhanced edge extension. The Python implementation matches predicted bounds, generates valid witnesses, and extends the framework to deterministic FNP computation.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages113

Reading Time4 h 45 min

Introduction

Related Work

Background and Preliminaries

Explicit Turing Machines for NP-Complete Problems

Efficient Construction of Feasible Graphs

Improvements by Restricting Candidate Set for Verification

Implementation Details and Practical Improvements

Experimental Evaluation

Discussion and Future Work

Conclusion

arXiv :2602 . 1099 1v4 [ cs .CC] 12 Jul 2026 Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework Changryeol Lee∗† July 14, 2026 Abstract 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 certificate-oblivious verifier Turing machines 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, is available in a public online repository. Contents 1 Introduction 3 2 Related Work 4 3 Background and Preliminaries 5 3.1 Deterministic Turing Machines and Computation Graph ...................... 5 3.2 Feasible Graph and Computation Walk Verification ......................... 9 3.3 Overview of Polynomial-Time NP Verifier Simulation Framework ................. 12 4 Explicit Turing Machines for NP-Complete Problems 15 4.1 SAT Turing Machine with Input-Dependent States .......................... 16 4.2 SAT Turing Machine With Fixed States ................................ 23 4.3 Subset-Sum Turing Machine ...................................... 29 4.4 Restriction of Certificate Symbols for Input Sanitization ....................... 37 4.5 Refined Bounds of the Footmarks Graph ............................... 39 5 Efficient Construction of Feasible Graphs 41 5.1 Efficient Cover Edge Computation ................................... 41 5.2 Complexity Improvement in Feasible Graph Construction ...................... 44 5.3 Impact of Improved Feasible Graph Construction .......................... 53 6 Improvements by Restricting Candidate Set for Verification 57 6.1 Walk-First Strategy Prior to Edge Extension via verification ..................... 57 6.2 Theoretical Reduction of Candidate Edges .............................. 61 6.3 Extraction of FNP Witnesses from Accepted Walks ......................... 73 ∗Independent Researcher [changryeol@kaist. ac. kr](changryeol@kaist. ac. kr) †The primary research for this work was conducted while the author was affiliated with the Department of Software, Yonsei University. 7 Implementation Details and Practical Improvements 73 7.1 Practical Improvements for Extending Futile Edges ......................... 74 7.2 Implementation of Turing Machines .................................. 75 7.3 Additional Methods for Dynamic Computation Graphs ....................... 77 7.4 Implementation of Dynamic Array ................................... 78 7.5 Additional Possible Data-Structure Optimizations .......................... 81 8 Experimental Evaluation 81 8.1 Experimental Setup ........................................... 82 8.2 Test Case Design and Metrics ...................................... 82 8.3 Experimental Results for 3SAT with Input-Dependent TM ..................... 83 8.4 Experimental Results for Fixed-State SAT Turing Machine ..................... 85 8.5 Experimental Results for Sum-of-Subset ................................ 87 8.6 Observations and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 9 Discussion and Future Work 89 10 Conclusion 90 A Ordinary Verifier Turing Machines 93 A.1 Input-Dependent Verifi

FAQs

What gap does the paper address in the verifier-simulation framework for NP?

The framework existed formally, but explicit executable deterministic Turing machines and concrete implementation details for specific NP-complete problems were missing. This paper provides implementation-oriented realizations for SAT and Subset-Sum.

Which NP-complete problems are given explicit deterministic machine implementations?

The paper constructs fully specified deterministic certificate-oblivious verifier Turing machines for SAT and Subset-Sum.

How do the paper’s improvements affect theoretical and practical performance?

A refined feasible-graph construction reduces the asymptotic polynomial degree, while enhanced edge extension mechanisms improve practical execution speed.

Jul 16, 2026

Upload by Himbo