Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Graph-Based Deterministic Polynomial Framwork for NP Problems

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper claims a graph-walk algorithm that solves every NP problem in polynomial time, thereby proving P = NP.

desk verdict The P=NP proof fails at the local edge rule: Definition 12 allows spurious walks that Algorithm 8 can certify, and the pruning correctness assumes the very exponential object it should avoid. read the letter →

arxiv 2508.13166 v8 pith:MJJC3DPC submitted 2025-08-02 cs.CC

Changryeol Lee (Independent Researcher) This is my paper · ORCID
classification cs.CC MSC 68Q1568Q0568Q17
keywords P=NPpolynomialtimefeasiblegraphcomputationcertificate-obliviousverifierTuringmachinesimulationNPdecisionproblemscomplexityclasses
topics P versus NP
open problems 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

The paper claims a constructive resolution of the P versus NP question: a single algorithm, SimulateVerifierForAllCertificates(), that decides any NP problem in deterministic polynomial time. Its strategy is to simulate, not the nondeterministic machine, but the polynomial-time verifier: all certificate computations are drawn as edges in one layered "computation graph," and the paper argues that overlapping walks keep the edge set polynomially bounded. A pruning procedure builds a "feasible graph" that is claimed to delete every spurious edge while preserving every genuine computation walk ending at a chosen final edge, so that deciding membership reduces to graph reachability. If the construction is right, the exponential search over certificates is replaced by incremental edge extension, and P = NP follows in time polynomial in the input length. A fair reader should understand the paper as offering not a complexity-theoretic barrier argument but a concrete, mechanistic route from verifier to decider.

What carries the argument

The load-bearing object is the feasible graph. Starting from the footmarks graph, the union of all edge sets of all certificate walks, the construction deletes every edge in the maximal step-extended component rooted at step-pendant edges, which are edges that are pendant, or lack a precedent, or lack a succedent and are not cover edges, while keeping the designated final edges and initial vertices. Cover edges are edges connected to a target final edge by a chain of ceiling-adjacency relations, and the pruning is claimed to remove exactly the obsolete walks so that every walk ending in a target final edge survives. Supporting this object are the certificate-oblivious verifier, whose head movement is independent of certificate contents and thereby aligns all walks onto shared edges, and the tier structure that records per-cell visit counts so that precedent and succedent relations stay locally checkable. The work this machinery does is to convert the existential question "does some certificate accept?" into a reachability question in a polynomially sized graph, which VerifyExistenceOfWalk() answers by iterated pruning of computing-redundant and computing-disjoint edges.

What would settle it

A concrete refutation would be a small instance where VerifyExistenceOfWalk() disagrees with brute force: run the paper's deterministic construction on a 3-SAT formula with six variables (64 possible certificates) and compare its verdict with exhaustive enumeration over those certificates, since any mismatch in either direction shows that Theorem 30 is false. A more surgical experiment is to search the constructed graph for a spurious walk, a path that returns to a previously visited cell and reads a symbol different from the one that cell's last transition actually wrote, which would pass the local reachability test yet correspond to no real certificate.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 30: the algorithm SimulateVerifierForAllCertificates() decides every NP language in deterministic polynomial time, so P = NP. The argument models each tape cell of a verifier Turing machine as a stack of computation nodes (a node records cell index, current state, current symbol, last state, last symbol, and a tier counting how many times the cell was visited), and draws an edge between nodes whenever a single transition moves the head from one cell to the next. Running the verifier on all certificates at once, the walks crowd onto a shared graph, and the paper claims the overlap keeps the edge count polynomial. A certificate-oblivious verifier, whose head movements do not depend on certificate contents, is introduced to force all walks to align their transitions. A feasible graph is then defined by pruning step-pendant edges while preserving every walk that ends in a chosen final edge, and VerifyExistenceOfWalk() checks in polynomial time whether any such walk reaches a target edge; the main algorithm repeatedly extends the visited graph boundary with verified edges until an accepting state is reached or no extension exists. The paper concludes with a polynomial bound of O($h^{12}$ $w^{5}$) on the whole simulation, with width w and height h of the graph.

Load-bearing premise

The proof assumes that any chain of edges in the computation graph, each a single locally reachable transition, is a genuine computation walk of the verifier for some certificate; it never shows that the tape history a node records (its surface and precedent) is enforced along graph paths, and the verification algorithm treats reachability as sufficient evidence of a valid run.

Editorial extensions

If this is right

  • NP = co-NP = P: with every NP language decidable in polynomial time, complements are decided by flipping the answer, so the polynomial-time hierarchy above P collapses to P.
  • Every NP-complete problem, including the Boolean satisfiability problem used to build the universal verifier, gains a deterministic polynomial-time decider under the paper's construction.
  • Certificate search is replaced by graph extension: an accepting certificate exists exactly when the feasible graph, grown boundary edge by boundary edge, reaches an accepting state, and no certificate string ever needs to be written down.
  • The author notes the collapse would remove the worst-case hardness assumptions underlying most public-key cryptography, while also conceding that the constructed algorithms carry polynomial exponents and overhead too large for immediate practical use.

Reading between the lines

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

  • Because the construction is fully deterministic, a testable check is to run VerifyExistenceOfWalk() on small formulas and compare its verdict with exhaustive certificate enumeration: any disagreement on a small instance would be an explicit counterexample to Theorem 30.
  • The proof's soundness turns on whether local edge reachability enforces global tape consistency; a reader could search the constructed graph for a walk whose return to a previously visited cell reads a symbol different from the one that cell's last transition actually wrote, which would reveal a spurious accepted walk.
  • If the edge-compression idea is sound, it should transfer to alternating quantifiers and collapse PSPACE to P by the same feasible-graph trimming; a failure there would localize where the argument depends on the single existential quantifier of NP.
  • Manuscript-stated caveat: the proof of Theorem 30 concedes that the time-complexity analysis omits the dynamic-array data-structure overhead and patches it only at the end with an extra polynomial factor, so the stated O(h^12 w^5) is a clean-model bound rather than an implemented runtime.
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

4 major / 5 minor

Summary. The paper claims a constructive proof that P=NP by introducing a graph-based computation model in which computation nodes are 6-tuples (cell index, state, symbol, last state, last symbol, tier) and edges represent single deterministic verifier transitions. The authors define computation walks, feasible graphs, pruning operations, and an algorithm VerifyExistenceOfWalk that is supposed to decide in polynomial time whether a computation walk to a given final edge exists. They then use this verifier inside SimulateVerifierForAllCertificates to decide any NP language without enumerating certificates, concluding P=NP in Theorem 30.

Significance. If the construction were correct, it would be an extraordinary result: an explicit deterministic polynomial-time decision procedure for every NP language, collapsing P, NP, and co-NP and invalidating the complexity-theoretic assumptions underlying much of cryptography. The paper is unusually explicit about its graph definitions and provides lemma-level proofs for every algorithmic component, which makes the point of failure easy to localize. It also correctly notes that the relativization, natural-proof, and algebrizing barriers do not by themselves rule out P=NP. However, the central soundness gap in the local edge predicate and the circular reliance on the hidden set of all valid computation walks invalidate the main theorem as written, so the claimed significance is not achieved.

major comments (4)
  1. [§4.1, Definitions 12–13; §6.3, Lemma 22] Definition 12 creates an edge (u,v) whenever |index(v)-index(u)|=1 and v's configuration is reachable from u by a single transition. For a deterministic Turing machine this permits edges from u to many nodes v with state(v)=next_state(u) and index(v)=next_index(u), for all symbols and all last-state/last-symbol combinations at the destination cell. Definition 13 then calls any sequence of such edges a computation walk. Consequently, a graph path can revisit a cell and enter a node whose symbol and last state do not match the last transition at that cell on the same path. Lemma 15 and Lemma 22 prove preservation of feasible walks by induction on walks under the assumption that output(Prec(v))=symbol(v) and that the precedent edge actually occurred earlier on the same path; Definition 12 enforces neither condition. Since Algorithm 8 treats reachability in this graph as certificate validity, spurious walks can cause acceptance for inputs no certificate accepts, breaking the soundness of Lemma 22 and hence of Theorem 30.
  2. [§5, Definitions 32 and 34; §6.1, Sublemmas 5–7 and Lemma 17] The correctness proofs for the polynomial pruning procedure depend essentially on the set W of all valid computation walks, which the algorithms never possess. Definition 34 classifies walks as feasible, obsolete, or orphaned only relative to some W of computation walks; Lemma 16 reasons about walks W′,W′′∈W∖{W}; and Sublemmas 5–7 and Lemma 17 assume properties of all walks in W. Algorithm 4 and Algorithm 7, however, receive only a graph, an initial vertex set, and a final edge set, and must construct or prune without enumerating W. Thus the proof that the pruned graph preserves all walks to the target edge presupposes the exponential object the algorithm is supposed to replace. This circularity is load-bearing and cannot be removed by local graph bookkeeping.
  3. [§7.2, Lemma 27] Lemma 27's soundness argument claims that a spurious walk leads to a contradiction because GetNextEdges generates only edges consistent with the verifier's transition rules. This is insufficient: individual transition consistency is exactly the property that the local edge rule of Definition 12 does not preserve along graph paths. A path may be composed of locally valid δ-steps yet read a certificate cell with a symbol written differently earlier on the same path. The lemma never constructs the certificate y whose execution realizes the purported walk; the graph-to-run correspondence is asserted, not proved. The 'only if' direction of Theorem 30 therefore remains unsupported.
  4. [§4.4, Lemma 6; §7.3, Theorem 30] The polynomial-size bound in Lemma 6 is not justified by the graph construction. The proof states that a node may have up to O(p(n)) outgoing edges because the height is O(p(n)), but under Definition 12 the number of possible next nodes from a given node is determined by the alphabet, state set, and the tier of the destination, all constants, not by the height. The authors would need to replace this argument with a correct bound; the current proof does not establish the claimed O(p(n)^3) edge count on which the final O(h^12 w^5) runtime of Theorem 30 relies.
minor comments (5)
  1. [§3.1, after Definition 6] The sentence 'This formulation is known as the certifier-based definition of NP.' appears twice in consecutive paragraphs; one occurrence should be deleted.
  2. [§4.4, Algorithm 3, certificate-branching branch] In the branch at line 20–29, the recursive call is written as `ProceedToNextNodes(v′,S′,W,L,m)`, but the function signature is `ProceedToNextNodes(G,v,S,W,Γ,L,m)`. The call omits the graph argument, omits Γ, and passes the un-copied W instead of the copied W′; it should presumably be `ProceedToNextNodes(G,v′,S′,W′,Γ,L,m)`.
  3. [§4.4, Lemma 5 proof] In the proof, the text says 'define q′ = next_index(v) as the next state of the Turing Machine'; this should be q′ = next_state(v).
  4. [§5.1, Lemma 15 statement] Lemma 15 says 'a set of edges Ef∖EFINAL' but the intended hypothesis is clearly Ef⊆EFINAL; as written, Ef∖EFINAL is empty and the statement is vacuous.
  5. [Throughout] There are numerous typographical errors, including 'Framwork' in the title metadata, 'Compuation walk' in the Section 6 heading, 'algortihm' in Section 5.2, 'probelms' in Theorem 30, and 'Initilize' in Algorithm 11. These do not affect the technical arguments but should be corrected in any revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No enumerated circularity; the central objection is a soundness gap, not a circular reduction.

full rationale

Walking the derivation chain, I find no circular step of the seven enumerated kinds. The paper contains no self-citations and invokes no uniqueness theorem or ansatz imported from the authors' prior work; there are no fitted parameters being relabeled as predictions. The serious concern raised by the reader—that Definition 12's local edge condition does not enforce surface/precedent consistency along graph paths, so Algorithm 8 may certify walks not realizable by any certificate—is a soundness/correctness gap between the graph reachability relation and the intended Turing-machine run semantics. That is not a circular reduction: the graph construction and the feasibility pruning are stated in terms of the graph's own local rules, and the correctness proofs use the semantic set W of valid computation walks as the specification being proven, rather than as an input to the algorithm. Using W in a correctness invariant is standard methodology and does not make the algorithm's output equivalent to its input by construction. Therefore the result is not circular under the stated criteria, and the score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The proof relies on an unproven identification between local graph paths and real verifier runs, and its pruning correctness assumes access to the full set W of valid walks. No free parameters are fitted to data; the central weight is carried by these modeling axioms.

assumptions (4)
  • standard math CSAT is NP-complete, so every NP language has a fixed universal verifier via polynomial-time reduction.
    Used in Lemma 1 to fix a single verifier machine; accepted from Cook's theorem, but the universal verifier's specific instruction set is never given.
  • ad hoc to paper Every path in the computation graph corresponds to an actual run of the verifier on some certificate.
    Invoked by Definition 13 and used throughout Algorithm 8. It is false because Definition 12's local edge predicate does not verify that a walk enters each higher-tier node only after visiting that cell at the previous tier on the same path.
  • ad hoc to paper The feasible graph can be constructed and verified for correctness using only local graph operations.
    Assumed in Algorithms 4-10. The proofs instead use the global set W of valid walks (Definition 34), which is not available to the polynomial algorithm.
  • domain assumption The union graph's width and height are O(p(n)), where p(n) bounds the verifier's runtime.
    Used in Lemma 6 and all complexity lemmas. Local nodes are bounded by |Q||Gamma|^2, but tape-content variation over p(n) cells is ignored, so the bound does not follow for global configurations.
invented entities (2)
  • Computation graph with tiered local nodes (cell index, state, symbol, last state, last symbol, tier)
    purpose: Collapse all possible verifier states into a polynomial-size graph.
    No independent empirical handle exists; its adequacy for representing real computations is the central unproven assumption.
  • Feasible graph and step-extended components
    purpose: Prune non-feasible walks in polynomial time.
    Defined in terms of W, the set of all valid walks, so it cannot be constructed or validated from graph-local information alone.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph-Based Deterministic Polynomial Framwork for NP Problems." pith.science (2026). https://pith.science/paper/MJJC3DPC

@misc{pith2026250813166,
  author       = {Pith},
  title        = {Pith review of: Graph-Based Deterministic Polynomial Framwork for NP Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MJJC3DPC}},
  note         = {Machine review of arXiv:2508.13166}
}
read the original abstract

The P versus NP problem asks whether every language verifiable in polynomial time can also be decided in deterministic polynomial time. In this paper, we present a constructive proof that P=NP by introducing a universal, graph-based deterministic framework applicable to all NP problems without requiring reduction to an NP-complete problem. We model computational transitions as edges within a unified graph structure, where edges correspond to the steps of a deterministic verifier Turing machine for all possible certificates. Due to the overlap of edges among computation paths, the total cardinality of the edge set remains polynomially bounded. Furthermore, by employing a certificate--oblivious verifier Turing machine--whose head movement is independent of the certificate contents--we force all computation paths to align their edge transitions. A key feature of our approach is that each extension step enforces global consistency via a local infeasibility trimming tool. This mechanism systematically preserves valid NP paths that lead to the target edge under polynomial verification, ensuring the graph remains globally feasible at every stage without explicit enumeration. This represents a paradigm shift from searching over exponential certificates to the incremental extension of verified edges. Since our construction decides all NP problems in deterministic polynomial time, it provides a direct resolution to the P versus NP question and demonstrates that every NP problem can be solved in deterministic polynomial time via incremental graph edge extension.

Figures

Figures reproduced from arXiv: 2508.13166 by the authors.

Figure 1
Figure 1. Turing machine Computation Model For an instruction I = (q, σ, σ′ , d, q′ ), let eI be an edge that can be added by instruction I. Then eI belongs to V q,σ i,t × (∪s∈Γ,t′∈N0 V q ′ ,s i+d,t′ ) for some i ∈ Z where N0 = N ∪ {0} and t ∈ N0. Definition 14. The index of an edge e = (u, v) is defined as the smaller of index(u) and index(v), and is denoted by index(e). The direction of an edge e = (u, v) is defined as dir(… view at source ↗
Figure 2
Figure 2. Incoming Folding Edge Direction with tier >0 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Turing Machine Taple Area For Verifier Each edge is stored using four adjacency lists per node: • left_incoming, left_outgoing, right_incoming, and right_outgoing, depending on the direc￾tion and position of the head movement. • Using these lists, checking whether an edge is a folding edge, or whether it is adjacent to a layer Ei−1 or Ei+1, can be done in constant time. • Retrieving all incoming or outgoing edges of… view at source ↗
Figures from the paper (2 more)
Figure 6
Figure 6. Figure 6: No Floor Orphaned Edge Proof. Let W be an orphaned walk containing the first orphaned edge e = (u, v) in W. By the definition of an orphaned edge, there exists an edge of W that belongs to GO but not to the feasible graph G. Therefore, there exists a walk W′ in G that …
Figure 8
Figure 8. Figure 8: Case When W′ f ∩ W ̸= Wf ∩ W. 2. e ∈ W ∩ Wf for some feasible walk Wf : Let Wf be a feasible walk eliminated at step k and let W′ f be the attempted walk Wk whose pruning removed Wf from the feasible graph (i.e., Wf exists in G(k−1) but not in G(k) ). Since pruning doe…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    cs.CC 2026-02 reject novelty 5.0 of 10

    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 polynomia...

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages · cited by 1 Pith paper

  1. [1]

    Aaronson and A

    S. Aaronson and A. Wigderson. Algebrizing proofs: The case of ip = pspace.Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 447–456, 2008

    work page 2008

  2. [2]

    Baker, J

    T. Baker, J. Gill, and R. Solovay. Relativizing proofs of the p = np problem.SIAM Journal on Computing, 4(4):297–309, 1975

    work page 1975

  3. [3]

    Stephen A. Cook. The complexity of theorem-proving procedures.Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC), pages 151–158, 1971

    work page 1971

  4. [4]

    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

    work page 1972

  5. [5]

    Graduate texts in mathematics: Graph theory

    Reinhard Diestel. Graduate texts in mathematics: Graph theory. Heidelb: SpringerVerlag, third edition edition, 2005

    work page 2005

  6. [6]

    Jones and Bartlett Publishers, Inc., 1996

    James L Hein.Theory of computation: an introduction. Jones and Bartlett Publishers, Inc., 1996

    work page 1996

  7. [7]

    Introduction to automata theory, languages, and computation

    John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60–65, 2001

    work page 2001

  8. [8]

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

    work page 1972

Show all 11 references
  1. [9]

    Pearson, Upper Saddle River, NJ, June 2005

    Jon Kleinberg and Eva Tardos.Algorithm Design. Pearson, Upper Saddle River, NJ, June 2005

    2005

  2. [10]

    Razborov and S

    A. Razborov and S. Rudich. Natural proofs.Journal of Computer and System Sciences, 55(1):24–35, 1993

    1993

  3. [11]

    Introduction to graph theory.Tata McGraw-Hill, pages 2–10, 2005

    Ping Zhang and Gary Chartrand. Introduction to graph theory.Tata McGraw-Hill, pages 2–10, 2005. 54 A Terminology and Definitions Table 2: Summary of Key Terms and Definitions(Computation Graph) Term Description Reference Computation Walk A sequence of edges on the computation ...

    2005

Pith tools

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