{"id":"757795e7-d399-4924-8b82-b30601c90805","arxiv_id":"2602.10991","paper_version":4,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper adds concrete verifier Turing machines and an improved feasible-graph algorithm to the author's prior framework, which claims deterministic polynomial-time decision for SAT and Subset-Sum; the core polynomial-time claim is neither proven nor independently verified in this paper.","lead":"This paper presents explicit deterministic Turing machines for SAT and Subset-Sum together with graph-pruning improvements, and claims that this yields a polynomial-time simulation of NP verification. The decisive polynomial-time claim is inherited from the author's own earlier framework [4], which is cited rather than re-proven or machine-checked here.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim inherits the unproven feasible-graph preservation theorem from [4]; the paper explicitly defers foundational analysis (Lemma 14, Remark 3), so the polynomial-time SAT/Subset-Sum decision is unsupported.","rationale":"The reader correctly identified the weakest assumption: the correctness of the feasible-graph/walk-verification framework is imported from the author's earlier work [4] and not re-proven. My review of the full text confirms this. The paper's own presentation flags the dependency: Remark 2 and Remark 3 quote facts from [4], Section 3.3 says 'we adopt this construction,' and Lemma 14 explicitly directs readers to the original framework for foundational analysis. The improved algorithms (Sections 5 and 6) are presented as refinements that preserve correctness, but their proofs (Sublemma 1, Lemma 11, Lemma 12) rely on the same imported facts — e.g., the assertion that every ceiling edge is a cover edge is taken from [4] without independent verification. The central claim is therefore a claim-without-derivation. This is not a disagreement with consensus; it is a correctness risk: if the imported preservation theorem is false, or if the new cover-edge computation omits a ceiling edge despite the claimed completeness, the algorithm can produce a wrong decision for SAT or Subset-Sum, directly refuting the P=NP conclusion. The suggested analytical test — re-deriving the preservation lemmas from first principles — would settle whether the concern lands. The empirical exhaustive test provides a practical cross-check. Given this, the reader's REJECT verdict is appropriate; my analysis does not change it.","tokens_in":48645,"tokens_out":6397,"duration_ms":61849,"concrete_test":"Independently prove Sublemma 1 (Completeness of Improved ComputeCoverEdges) and Lemma 12 (Preservation of Feasible Walks) using only the definitions in Section 3 (Definitions 20-27) and the transition rules given, without invoking Remark 3 or any result from [4]. If either proof requires an additional unstated assumption or fails, the central construction has a hidden gap. As a complementary empirical check, run the provided implementation on all 3-SAT formulas with up to 20 variables and compare accept/reject against a brute-force solver; any mismatch refutes the claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim — that SimulateVerifierForAllCertificates() decides SAT and Subset-Sum in O(n^19 log n) time — depends entirely on the correctness of the feasible-graph machinery: that the feasible graph preserves exactly the edges lying on valid computation walks to the target edge, so that VerifyEdgeExtension/VerifyExistenceOfWalk correctly decides extendability. This is the load-bearing premise. The paper does not re-prove it. It explicitly adopts the construction from [4] (§3.3: 'we adopt this construction'), imports key structural facts as quoted remarks (Remark 2: 'It was shown in [4]'; Remark 3: 'Following the results in [4], every ceiling edge is categorized as a cover edge. We adopt this fact'), and Lemma 14 states 'For a complete foundational analysis, readers may refer to the original framework.' The improved feasible-graph algorithm (Algorithms 4-6) is claimed correct by Sublemma 1 and Lemma 12, but these proofs themselves rely on the same imported ceiling-edge/cover-edge fact and on the existence of the framework's preservation theorem. The paper's stated objective is 'not to alter or strengthen the core proof of the original paper,' so the extraordinary P=NP consequence stands on an unverified, unavailable foundation. If the feasible-graph preservation property fails — e.g., if the pruning removes an accepted walk or the cover-edge set misses a ceiling edge — the algorithm can reject a satisfiable instance or accept an unsatisfiable one, invalidating the headline claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":48900,"tokens_out":8681,"duration_ms":80312,"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":[{"comment":"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","section":"§3.3, Remarks 2–3, Lemma 14"},{"comment":"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].","section":"§5.2, Lemmas 11–12"},{"comment":"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.","section":"§6.2, Lemma 18"}],"minor_comments":[{"comment":"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.","section":"§4.5, §5.3"},{"comment":"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'.","section":"Algorithms 1 and 6"},{"comment":"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.","section":"Definition 31 and Remark 5"},{"comment":"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.","section":"§4.4"},{"comment":"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.","section":"Abstract and §4.5"}],"recommendation":"reject","confidential_remarks":"The manuscript's central claim is conditional on the author's own framework [4], which is not available in the submitted material and is not proved in this paper. The editor should verify whether [4] is published and peer-reviewed; if not, the paper cannot be considered for publication in a serious journal. The verifier-machine constructions and implementation work are substantial, but they are secondary to the unsupported P=NP-level claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing to know: this paper does not prove P=NP, and it does not claim to. It says so itself — the stated objective is \"not to alter or strengthen the core proof of the original paper.\" The core proof lives in the author's earlier framework [4], which this paper adopts wholesale (§3.3). So the polynomial-time SAT and Subset-Sum claim stands or falls on [4], not on anything derived in this manuscript.\n\nWhat is actually here is real, careful work. Fully specified verifier TMs for SAT and Subset-Sum with transition tables (§4.2–4.3), a refined structural analysis giving w=h=O(n) and O(n^19 log n) total simulation (§4.5), an improved feasible-graph construction claimed at O(wh^3 log wh) versus the original O(w^2 h^4(h log h + log w)) (§5), a restricted candidate-edge scheme (§6), and FNP witness extraction. The verifier soundness and completeness lemmas (1–10) are standard, checkable, and fine. The paper is also honest in the right places: the input-dependent SAT machine is flagged as non-classical, and the reliance on [4] is stated plainly rather than hidden.\n\nThe soft spot is the one the paper flags itself. Lemma 14, Remarks 2–3, and the §3.3 overview all defer the foundational analysis to [4]. The entire engine — the feasible graph preserves exactly the edges that can lie on a valid computation walk to the target, and VerifyExistenceOfWalk terminates in polynomial time — is imported, not re-proven. The internal lemmas (11–13) are mostly conditional on that machinery; their proofs lean on the same imported ceiling-edge/cover-edge facts. And the verification procedure is semantically the decision problem itself, so if the preservation property fails anywhere, the pruning can erase the only accepting walk or run exponentially. That is a load-bearing gap, not a cosmetic one.\n\nMinor issues: the transition tables are garbled in the text, \"bCE\" is referenced but never defined, and the text we saw cuts off mid-§6, so the experimental and limitations sections were not auditable.\n\nWho this is for: a referee tracing where the framework breaks, or someone working through the author's program. The portable pieces are the verifier TMs and the complexity refinements; I would not cite it this year. But I would send it to a careful referee rather than desk-reject it. The claim is extraordinary, the scaffolding is substantial, and a serious review that pins down which imported fact fails would be the most useful outcome.","headline":"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.","tokens_in":49508,"tokens_out":5516,"would_cite":false,"duration_ms":48888,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["NP verifier simulation","P vs NP","SAT","Subset-Sum","feasible graph","step-pendant edge","deterministic Turing machine","FNP"],"falsifier":"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","tokens_in":48344,"feed_emoji":"🧮","tokens_out":7138,"duration_ms":65381,"temperature":0.7,"pith_summary":"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.","feed_headline":"Simulator claims polynomial-time decision for SAT and Subset-Sum","feed_subtitle":"If the feasible-graph pruning holds, the same routine gives P = NP and extracts witnesses at no extra cost.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Executable verifier claims poly-time for SAT and Subset-Sum","Closed-form verifier machines target P=NP with O(n^19)","From proofs to code: SAT and Subset-Sum in O(n^19)","Deterministic verifier simulators for SAT and Subset-Sum","NP verifier framework yields executable poly-time for NP-complete"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Executable verifier claims poly-time for SAT and Subset-Sum","Closed-form verifier machines target P=NP with O(n^19)","From proofs to code: SAT and Subset-Sum in O(n^19)","Deterministic verifier simulators for SAT and Subset-Sum","NP verifier framework yields executable poly-time for NP-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000202,"raw_usage":{"total_tokens":1182,"prompt_tokens":667,"completion_tokens":515,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":411,"completion_tokens_details":{"reasoning_tokens":431}},"tokens_in":411,"tokens_out":515,"duration_ms":5152,"temperature":1.0,"reasoning_tokens":431,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T00:55:08.650830+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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","supporting_citations":[],"review_version":2}