Pith. sign in

REVIEW 3 major objections 5 minor 5 references

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

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims to construct explicit deterministic verifier machines for SAT and Subset-Sum and to simulate all certificates in polynomial time O(n^19 log n), which would make P equal to NP.

desk verdict Implementation companion to a same-author P=NP framework: the verifier TMs and complexity refinements are real, but the load-bearing walk-preservation theorem is imported from [4], so the headline claim is unsupported here. read the letter →

arxiv 2602.10991 v4 pith:ZHHU72LA submitted 2026-02-11 cs.CC cs.FL

Changryeol Lee (Independent Researcher) This is my paper · ORCID
classification cs.CCcs.FL
keywords NPverifiersimulationPvsSATSubset-Sumfeasiblegraphstep-pendantedgedeterministicTuringmachineFNP
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper is an implementation-oriented realization of an earlier NP verifier simulation framework that claims to simulate, deterministically and in polynomial time, the exponential search over all possible certificates of an NP verifier. It constructs fully specified single-tape verifier machines for SAT (two variants) and Subset-Sum, and it gives a Python implementation of the graph-based pruning algorithms that drive the simulation. The central claim is that the total running time is bounded by O(n^19 log n), a polynomial, which would make SAT and Subset-Sum—and every NP problem with an explicit verifier machine—decidable in deterministic polynomial time. The paper also claims that the simulation outputs a valid certificate whenever it accepts, extending the result to deterministic FNP computation without extra asymptotic cost. A sympathetic reader would care because the paper offers a constructive, executable route to the most famous open problem in computer science, though the correctness ultimately rests on a graph-theoretic preservation lemma carried over from the earlier framework.

What carries the argument

The central object is the 'feasible graph': a pruned subgraph of the Turing machine's computation graph that keeps exactly the edges that can belong to a valid computation walk ending at a designated final edge. The paper computes it in a new way—first computing a superset of 'cover edges' (edges whose ceiling-adjacency chains propagate toward the final edge) via a single backward reachability pass, then repeatedly removing 'step-pendant' edges (edges with no index-predecessor, no index-succedent unless they are cover edges, or pendant horizontally) with a queue, until stabilization. Around this core sit the computation graph of 'footmarks' (the union of all walks seen so far), a walk-verifi

What would settle it

A concrete counterexample would be a small deterministic verifier computation where the step-pendant removal procedure deletes an edge that belongs to the only accepting computation walk, causing a false rejection; running the released simulator on the smallest unsatisfiable 3-SAT instances and checking that pruning decisions never remove an edge that later appears in an accepted walk would test this directly. A formal verification of the feasible-walk preservation lemma (Lemma 12) against the same data structures, or an explicit search over small computation graphs for a violation of that lem

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is that the feasible-graph machinery from the earlier framework can be turned into a closed, executable algorithm: the author defines explicit deterministic verifier machines for SAT (an input-dependent variant and a fixed-state variant) and Subset-Sum, gives improved definitions of cover/ex-cover edges and a queue-driven 'step-pendant' edge-removal procedure for computing feasible graphs, and then presents a routine SimulateVerifierForAllCertificates() that repeatedly verifies candidate edge extensions until an accepting walk is found or no extensions remain. The paper claims this routine runs in O(n^19 log n) time for both problems (with width and he

Load-bearing premise

The load-bearing premise is that the graph-theoretic pruning rule—that an edge classified as step-pendant can never lie on a valid computation walk to the accepting edge, so removing it preserves language membership—is correct and terminates in polynomial time; this premise is imported from earlier work rather than re-proved here, with the paper referring the reader to the original framework for the foundational analysis.

Editorial extensions

If this is right

  • SAT and Subset-Sum would both be decidable in deterministic polynomial time, placing them and every problem polynomial-time reducible to SAT in P.
  • The same framework would give deterministic FNP computation: whenever an instance is accepted, a valid certificate is reconstructed from the verified walk, with no increase in asymptotic time complexity.
  • The polynomial-time bound would transfer to any NP problem whose verifier Turing machine has explicit construction and linear width/height in the problem size, making the simulator a uniform NP decider for such problems.
  • The improved feasible-graph algorithm, if correct, would be a standalone structural result about computation graphs: feasible-walk preservation with an O(w h^3 log(w h)) construction cost.
  • The claimed reduction in the polynomial degree—from O(n^38 log n) to O(n^19 log n)—derives from the refined structural bounds w = O(n) and h = O(n) for the fixed-state verifiers, not from heuristic optimization.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the preservation lemma holds, the most surprising consequence is uniformity: the same simulator, given any explicitly constructed NP verifier machine, would become a polynomial-time decider for that NP problem, so no problem-specific algorithm design would be needed beyond writing the verifier.
  • Because the claimed exponent is large (n^19 log n), the practical value lies in structure rather than speed; even moderate n would be beyond reach, so a natural stress test is to force the pruning to remove an edge on the unique accepting walk of a hand-checkable small instance and see whether a false rejection occurs.
  • The refined w,h = O(n) analysis suggests the dominant cost could be attacked again at the graph-parameter level (for example, by shrinking certificate alphabets or exploiting additional structural restrictions), which the paper itself hints at when it says only structural refinements of the computation graph can reduce the degree further.
  • A testable extension is to instrument the released implementation to log every edge removed as step-pendant and verify, instance by instance, that removed edges never appear in any later accepted walk; systematic violations would localize any flaw before it scales.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper claims to provide fully specified deterministic certificate-oblivious verifier Turing machines for SAT and Subset-Sum, and to use an improved feasible-graph construction to simulate NP verification in deterministic polynomial time, with a headline bound of O(n^19 log n). It presents transition tables for three verifier machines, an input-dependent SAT verifier, a fixed-state SAT verifier, and a Subset-Sum verifier, together with soundness/completeness proofs for these machines. It then proposes a definition-faithful feasible-graph construction (Algorithms 3–6), a restricted candidate-set strategy for edge verification (§6), implementation details and an experimental evaluation on small instances. The overarching claim is that the whole framework runs in polynomial time and thereby decides SAT and Subset-Sum deterministically in polynomial time, with FNP witness extraction.

Significance. If the underlying feasible-graph preservation theorem were established, the paper would be a significant contribution: it gives explicit, executable verifier TMs for two NP-complete problems; it offers an improved feasible-graph algorithm with a lower asymptotic degree than the original framework; and it ships a reproducible Python implementation. The verifier-machine constructions themselves are detailed enough to be implemented and their per-certificate soundness/completeness proofs are plausible. However, the extraordinary consequence (deterministic polynomial-time decision of SAT and Subset-Sum) rests entirely on the feasible-graph machinery imported from the author's earlier framework [4]. The present paper explicitly declines to prove the foundational preservation theorem, and several structural facts used in the improved algorithms are quoted from [4] rather than proved. Consequently, the significance is conditional on an external, unavailable foundation, and the manuscript as it stands does not establish its main claim.

major comments (3)
  1. [§3.3, Remarks 2–3, Lemma 14] The central claim — that SimulateVerifierForAllCertificates() decides SAT and Subset-Sum in deterministic polynomial time — is not derived in this paper. The feasible graph is defined in Definition 27, but its load-bearing property, namely that it preserves exactly the edges that can lie on a valid computation walk to the target edge, is adopted from [4] ('we adopt this construction', §3.3). The structural facts in Remark 2 (floor edges iff tier-0) and Remark 3 (every ceiling edge is a cover edge) are quoted from [4], and Lemma 14 explicitly directs the reader to the original framework for 'a complete foundational analysis'. If this preservation property fails, the pruning can delete the only accepting walk or leave edges that do not correspond to any valid walk, invalidating both the decision procedure and the O(n^19 log n) bound. The abstract's P=NP-level conclusion is therefore unsupp
  2. [§5.2, Lemmas 11–12] Even granting the imported framework, the correctness proof of the improved feasible-graph construction is not self-contained. Lemma 12, Case 2, relies on the assertion that a ceiling edge belongs to the ex-cover edge set C; this is exactly Remark 3, which is adopted from [4] and not proved here. Lemma 11's completeness argument asserts that every edge that becomes step-pendant after a removal is enqueued by the propagation rules of Algorithm 6, but the four propagation cases are not shown to exhaust the step-adjacency/step-pendant conditions of Definition 24. Thus the correctness of the improved feasible-graph algorithm, and hence of the verification loop that depends on it, is not established independently of [4].
  3. [§6.2, Lemma 18] The restricted candidate-set theorem is incomplete. The proof of Lemma 18 breaks off mid-argument and refers to a 'sublemma 5' that is not stated in the manuscript. This restriction is the basis for the claimed reduction from O(wh^2) to O(wh) candidate edges per extension and for the practical correctness of the implementation. Without a complete proof that the restricted verification targets preserve acceptance behavior, the claim that the restricted implementation is correct is unsupported.
minor comments (5)
  1. [§4.5, §5.3] The headline bound O(n^19 log n) is derived in §4.5 using the original framework's T_f and VerifyExistenceOfWalk bounds. Section 5 later introduces an improved feasible graph with T_f=O(wh^3 log wh) and VerifyExistenceOfWalk=O(w^3 h^7 log wh), but the total simulation complexity under the improved construction is never recomputed. The relationship between the abstract's O(n^19 log n) and the algorithms actually implemented should be clarified.
  2. [Algorithms 1 and 6] There are several typos and minor errors: Algorithm 1 has 'compution graph'; Algorithm 6 line 1 calls ComputeCoverEdges(H, Ef) before H is defined, and line 6 says 'Dequeue from e Q'. Section 4.1 contains 'ghd Accept' and Table 1 contains 'clase termination'.
  3. [Definition 31 and Remark 5] The input-dependent SAT machine has a state set that grows with the input, so it is not a classical fixed-state Turing machine. The paper acknowledges this and later gives a fixed-state construction, but the role of the input-dependent construction in the framework should be stated more carefully: it is an illustration, not a uniform DTM verifier.
  4. [§4.4] The sentence 'Section 4.4 presents a transition fragment implementing this validation' is self-referential; the transition fragment appears in Table 6 of the same section. The reference should be to Table 6.
  5. [Abstract and §4.5] The term 'certificate-oblivious' is used in the abstract but is not defined in the paper. The machines presented are certificate-driven verifiers; the meaning of 'certificate-oblivious' should be clarified or removed.

Circularity Check

2 steps flagged · score 8.0 of 10

The polynomial-time NP decision is imported from the author's own framework [4], with the load-bearing feasible-graph preservation theorem deferred by self-citation rather than proved.

  1. self citation load bearing [Section 1 (Introduction); Section 3.3 (Overview of Polynomial-Time NP Verifier Simulation Framework)]
    "Throughout this paper, we adopt this construction, referred to as the Polynomial-Time NP Verifier Simulation Framework via Feasible Graph... The previous work establishes the existence of such a framework at a formal level. ... Our objective is not to alter or strengthen the core proof of the original paper, but to make its construction explicit, executable, and empirically verifiable on finite inputs."

    The paper's central theorem—that SimulateVerifierForAllCertificates() decides SAT and Subset-Sum in polynomial time—is the same claim as the author's earlier framework [4]. The correctness of the verification loop (VerifyEdgeExtension/VerifyExistenceOfWalk) rests entirely on the feasible-graph preservation property: that the feasible graph removes only edges that cannot belong to any feasible walk ending at the target edge. That property is not reproved here; it is imported by 'we adopt this construction' and by the statement that the previous work 'establishes the existence of such a framework at a formal level.' The paper even disclaims altering 'the core proof of the original paper.' Thus the headline polynomial-time NP decision is taken as input from [4], not derived.

  2. self citation load bearing [Section 3.2 Remarks 2-3; Section 5.2 Lemma 12; Section 5.3 Lemma 14]
    "It was shown in [4] that an edge e=(u,v) is a floor edge if and only if tier(v)=0. We will use this fact throughout the paper without further proof. ... Following the results in [4], every ceiling edge is categorized as a cover edge. We adopt this fact throughout our analysis. ... For a complete foundational analysis, readers may refer to the original framework."

    The feasible-walk preservation proof (Lemma 12) depends on imported floor/ceiling/cover-edge facts: a non-floor edge of a feasible walk has an index-precedent, a non-ceiling edge has an index-succedent, and ceiling edges are protected from step-pendant removal because they are cover/ex-cover edges. All these facts are asserted by citation to [4] rather than proved in this paper. Since [4] is the same author's framework that already contains the polynomial-time NP-simulation theorem, the correctness of the new feasible-graph algorithms is loaded from the very result the paper claims to implement and confirm.

full rationale

The verifier Turing machines themselves (M_SAT, M_SS) are described with self-contained transition tables and soundness/completeness proofs, so those portions are not circular. The circularity is in the decision layer: the algorithm's ability to decide SAT/Subset-Sum in polynomial time depends on the feasible-graph machinery preserving exactly all feasible computation walks. That preservation property is not established in this paper; Remark 2, Remark 3, and Lemma 14 explicitly defer to the author's own prior framework [4], and Section 1 states the paper's objective is not to strengthen or reprove the core proof. The O(n^19 log n) runtime claim is similarly obtained by substituting w=O(n), h=O(n) into the framework's quoted cost formulas O(w^4 h^8 T_f) and O(w^6 h^12(h log h + log w)), which are the complexity statements of [4]. If the imported preservation theorem fails, the pruning can delete the only accepting walk and both correctness and the polynomial bound collapse. The result is therefore forced by a self-citation chain rather than by an independent derivation, though the paper does contain substantial independent verifier-construction work.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

No numeric constants are fitted to data in the visible text; the claimed exponents (O(n^19 log n), O(w^3 h^7 log(wh))) are presented as derivations resting on the framework's correctness rather than on any empirical fit. The heavy debt is on the side of axioms: four of the five listed axioms are either imported from the same-author framework [4] or are unverified structural assumptions about the pruning machinery. One invented entity (the feasible graph) carries the entire polynomial-time decision property.

assumptions (5)
  • ad hoc to paper The NP verifier simulation framework of [4] correctly decides, in deterministic polynomial time, whether a candidate edge belongs to a valid computation walk ending at the target edge (and thus whether the NP language accepts the input).
    Adopted wholesale in §3.3 ('we adopt this construction'); correctness of VerifyExistenceOfWalk and VerifyEdgeExtension is deferred to [4] (Lemma 14: 'readers may refer to the original framework'); [4] is a same-author work with no verified artifact.
  • ad hoc to paper Every ceiling edge is a cover edge (Remark 3), and floor edges are exactly tier-0 edges (Remark 2).
    Stated as 'shown in [4]' / 'Following the results in [4]'. These structural facts underpin Lemma 12 (preservation of feasible walks) and the entire pruning logic.
  • domain assumption The improved ComputeFeasibleGraph with ex-cover edges preserves all feasible walks (Lemma 12) and removes exactly MSEC_G(E_R) (Lemma 11).
    Proved in-text, but the proofs rely on imported cover/ceiling facts and on informal 'first removed edge' arguments; treated as unverified domain assumptions for the central claim.
  • standard math The verifier TMs halt within p(n) steps on every certificate; width and height of the computation graph are O(n).
    Definition 2 and §4.5; standard complexity formulation. The per-certificate O(n^2) time and O(n) space claims (Lemmas 3, 6, 10) are plausible but not machine-checked.
  • standard math Ordered-set data structures with O(log) operations are used for membership and insertion (Remark 8).
    Stated assumption about implementation-level set operations, needed to validate the O(wh^3 log wh) bound of ComputeCoverEdges.
invented entities (1)
  • Feasible graph (with its walk-preservation property)
    purpose: The pruning substrate claimed to make verification of candidate edges polynomial-time (Definition 27, Algorithms 6–7).
    A new structural object whose load-bearing property — preserving exactly the feasible walks while removing step-pendant edges in polynomial time — is precisely the claim in dispute; no falsifiable handle exists outside the framework.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework." pith.science (2026). https://pith.science/paper/ZHHU72LA

@misc{pith2026260210991,
  author       = {Pith},
  title        = {Pith review of: Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZHHU72LA}},
  note         = {Machine review of arXiv:2602.10991}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2602.10991 by the authors.

Figure 1
Figure 1. Types of Combining edges index-succedent edges of these surface edges. This refined strategy reduces the per-edge verification bound to O(whTv), effectively eliminating a factor of h from the extension overhead and streamlining the overall simulation process. To formalize additional restrictions, we introduce the notion of a combined edge. Definition 36 (Combined and Proper Merging Edges). Let e = (u, v) and e ′ = (… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 1 linked inside Pith

  1. [4]

    Graph-based deterministic polynomial algorithm for np problems.arXiv preprint arXiv:2508.13166, 2025

    Changryeol Lee. Graph-based deterministic polynomial algorithm for np problems.arXiv preprint arXiv:2508.13166, 2025

    arXiv 2025

  2. [1]

    Time-bounded random access machines

    Stephen A Cook and Robert A Reckhow. Time-bounded random access machines. InProceedings of the fourth annual ACM symposium on Theory of computing, pages 73–80, 1972

    1972

  3. [2]

    A machine program for theorem-proving.Commu- nications of the ACM, 5(7):394–397, 1962

    Martin Davis, George Logemann, and Donald Loveland. A machine program for theorem-proving.Commu- nications of the ACM, 5(7):394–397, 1962

    1962

  4. [3]

    Richard M. Karp. Reducibility among combinatorial problems.Complexity of Computer Computations, pages 85–103, 1972

    1972

  5. [5]

    On computable numbers, with an application to the entscheidungsproblem.J

    Alan Mathison Turing et al. On computable numbers, with an application to the entscheidungsproblem.J. of Math, 58(345-363):5, 1936. 89 A Implementation Detail of Two SAT TMs The algorithms in this appendix detail the implementation of the transition function for the Turing machine in Section section 4, showing how concrete next states, output symbols, and...

    1936

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.