{"id":"821962b2-e0b9-4344-823f-bb3d126331c3","arxiv_id":"2508.13166","paper_version":8,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A claimed constructive proof of P=NP via polynomial-time graph simulation of all certificates.","lead":"This paper claims a constructive proof that P=NP, using a graph of local Turing-machine transitions to simulate all certificates deterministically in polynomial time. A generalist should read it because a correct P=NP proof would collapse major complexity classes, with sweeping consequences for cryptography, optimization, and artificial intelligence.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 12's local edge condition does not enforce surface/precedent consistency along paths, so Algorithm 8 can certify spurious walks and the soundness of the P=NP proof fails.","rationale":"The reader's weakest_assumption is precisely the spurious-walk / surface-enforcement problem, and I agree it is load-bearing. The paper's entire contribution is the claim that a polynomially sized graph of locally reachable transitions can be pruned to exactly the real computation walks; if graph reachability already admits impossible walks, then Lemmas 15, 22, 27, and 28 cannot establish correctness. The small-machine test directly probes the gap: constructing the graph per Definition 12 and running Algorithm 8 on a machine whose only accepting edge corresponds to an unread symbol is a minimal falsification attempt. If it succeeds, the central claim is unsupported and the REJECT verdict is appropriate. If it fails, the concern would be mitigated, though the proof would still need to state the missing invariant explicitly. The paper offers no machine-checked proofs or reproducible code that would independently support the construction, and the parameter count is zero, so there is no independent evidence to offset the gap. The reader's verdict of moderate-confidence REJECT is consistent with this stress-test.","tokens_in":47942,"tokens_out":8486,"duration_ms":104918,"concrete_test":"Take a verifier M with states {q0,qw,qa,qr}, alphabet {0,1}, that on any certificate y of length 1 writes 0 to the certificate cell, moves back to cell 0, then moves to cell 1 and accepts only if it reads 1 (so no real certificate is accepted). Build the computation graph exactly as in Definition 12 for input x=0, certificate length 1, with all tier-0 and tier-1 nodes and all allowed edges. Run VerifyExistenceOfWalk (Algorithm 8) on this graph with ef = the unique edge into qa. If it returns True (or if any graph path reaches qa), the spurious-walk concern is confirmed: the path reads a tier-1 symbol that was never written by the walk. If it returns False, this example does not break soundness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem (Theorem 30) rests on VerifyExistenceOfWalk (Algorithm 8) returning True iff a genuine computation walk to ef exists. But the paper's graph construction never proves that graph paths respect the tape surface or precedent histories. 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; since a transition does not alter the destination cell, this allows edges from u to every node v with state(v)=next_state(u), index(v)=next_index(u), for all possible symbols, tiers, and last-state/last-symbol combinations. Definition 13 then calls any sequence of such edges a computation walk. Consequently, a path can revisit a cell that was written earlier in the same path and read a node whose symbol is not the symbol last written there; such a path is not realizable by any certificate. Lemma 15 and Lemma 22 prove feasibility preservation by induction on walks, but the induction assumes that when a node v is entered, output(Prec(v)) equals symbol(v) and that the precedent edge actually occurred earlier on the same path. Definition 12 does not enforce either condition. Since Algorithm 8 treats reachability in this graph as certificate validity, spurious walks can make the polynomial algorithm accept inputs no certificate accepts, breaking soundness. This is not a gap in compute-theoretic consensus; it is an internal gap between the local edge rule and the global run semantics.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":48411,"tokens_out":9415,"duration_ms":118776,"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":[{"comment":"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.","section":"§4.1, Definitions 12–13; §6.3, Lemma 22"},{"comment":"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.","section":"§5, Definitions 32 and 34; §6.1, Sublemmas 5–7 and Lemma 17"},{"comment":"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.","section":"§7.2, Lemma 27"},{"comment":"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.","section":"§4.4, Lemma 6; §7.3, Theorem 30"}],"minor_comments":[{"comment":"The sentence 'This formulation is known as the certifier-based definition of NP.' appears twice in consecutive paragraphs; one occurrence should be deleted.","section":"§3.1, after Definition 6"},{"comment":"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)`.","section":"§4.4, Algorithm 3, certificate-branching branch"},{"comment":"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).","section":"§4.4, Lemma 5 proof"},{"comment":"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.","section":"§5.1, Lemma 15 statement"},{"comment":"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.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the headline: this is not the rare valid P=NP proof. The construction fails at Definition 12, where the local edge predicate does not enforce that a walk carries the surface and precedent history of higher-tier nodes. Algorithm 8 therefore can return true for spurious paths, and the soundness proof does not close that gap. On top of that, the pruning lemmas (Sublemmas 5–7, Lemma 17) explicitly rely on W, the hidden set of all valid walks, which is the exponential object the algorithm is supposed to avoid. That is a circularity, not a mere presentation issue.\n\nNow the credit. This is a serious attempt, not a crank mailing. The author builds a real formal apparatus: tiered computation nodes, transition cases, feasible graphs, step-extended components, and explicit pseudocode for each stage. The complexity bounds are written out, and the lemma structure is coherent. The idea of using a certificate-oblivious verifier to align edge transitions is original and worth recording. I believe the author is thinking clearly within the model; the problem is that the model's edge relation is too weak.\n\nThe stress-test note holds on reading. Definition 12 adds an edge whenever the configuration of v is reachable from u by one transition, which does not require that the symbol read at v matches the last symbol written at that cell on the same path. So a path can revisit a cell and pick a node whose symbol was not written there. Definition 13 blesses any sequence of such edges as a computation walk. The verification algorithm then treats reachability in this graph as certificate validity, which is exactly where an accept can be manufactured. Lemma 15 and Lemma 22 assume the precedent edge occurred earlier on the same path, but nothing in the graph enforces that. That is the load-bearing gap, and it is internal, not a disagreement with complexity folklore.\n\nThe W-circularity is just as serious. Feasible, obsolete, and orphaned walks are defined relative to W, and the pruning proofs invoke W to argue that certain edges can be removed. A polynomial algorithm cannot consult W, and the paper never shows that its feasible graph construction can be carried out without it.\n\nWho gets value from this? A complexity theorist wanting to see where graph-based verifier simulations tend to break, or a referee asked to formally document why the claim fails. The paper is not publishable as a solution to P vs NP, but it is serious enough to warrant referee time rather than a desk reject—assuming the editor is willing to spend it. My recommendation: send it to review with a note to the referee that Definition 12 and the W-dependence are the two places to focus on.","headline":"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.","tokens_in":48730,"tokens_out":3397,"would_cite":false,"duration_ms":42753,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q05","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims a graph-walk algorithm that solves every NP problem in polynomial time, thereby proving P = NP.","keywords":["P=NP","polynomial time","feasible graph","computation graph","certificate-oblivious verifier","Turing machine simulation","NP decision problems","complexity classes"],"falsifier":"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.","tokens_in":47744,"feed_emoji":"🧮","tokens_out":11478,"duration_ms":132953,"temperature":0.7,"pith_summary":"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.","feed_headline":"Paper claims graph walk algorithm solves every NP problem in poly time","feed_subtitle":"If right, it compresses all certificate checks into one overlapped graph, collapsing the P vs NP debate","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the NP-completeness of Boolean satisfiability, which Lemma 1 uses to build a single universal polynomial-time verifier that the simulation targets.","marker":"[3]"},{"why":"Provides the certifier-based definition of NP (Definition 6) that frames the whole approach as simulating a verifier over all certificates.","marker":"[9]"},{"why":"Gives the time-bounded RAM-to-Turing-machine simulation bound invoked in Theorem 30 to conclude the algorithm runs on a standard deterministic machine in polynomial time.","marker":"[4]"},{"why":"Supplies the formal Turing machine definition (states, alphabet, transition relation) on which computation nodes and computation walks are modeled.","marker":"[7]"},{"why":"Provides the graph-theoretic definitions of walks, paths, and induced subgraphs used throughout the computation-graph construction.","marker":"[5]"}],"fun_headline_variants":["Graph walk proof claims P=NP, solves all NP problems in poly time","New paper: graph-based verifier compresses NP checks to polynomial time","Certificate-oblivious verifier claims exponential search collapses to poly time","P=NP claimed via overlapping graph edges in new deterministic framework","Graph edge overlap argument aims to settle P vs NP with poly-time algorithm"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Graph walk proof claims P=NP, solves all NP problems in poly time","New paper: graph-based verifier compresses NP checks to polynomial time","Certificate-oblivious verifier claims exponential search collapses to poly time","P=NP claimed via overlapping graph edges in new deterministic framework","Graph edge overlap argument aims to settle P vs NP with poly-time algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000203,"raw_usage":{"total_tokens":1430,"prompt_tokens":1034,"completion_tokens":396,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":650,"completion_tokens_details":{"reasoning_tokens":302}},"tokens_in":650,"tokens_out":396,"duration_ms":5496,"temperature":1.0,"reasoning_tokens":302,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T05:44:55.557060+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the NP-completeness of Boolean satisfiability, which Lemma 1 uses to build a single universal polynomial-time verifier that the simulation targets."},{"cited_title":"Pearson, Upper Saddle River, NJ, June 2005","cited_arxiv_id":null,"evidence_quote":"Provides the certifier-based definition of NP (Definition 6) that frames the whole approach as simulating a verifier over all certificates."},{"cited_title":"Time-bounded random access machines","cited_arxiv_id":null,"evidence_quote":"Gives the time-bounded RAM-to-Turing-machine simulation bound invoked in Theorem 30 to conclude the algorithm runs on a standard deterministic machine in polynomial time."},{"cited_title":"Introduction to automata theory, languages, and computation","cited_arxiv_id":null,"evidence_quote":"Supplies the formal Turing machine definition (states, alphabet, transition relation) on which computation nodes and computation walks are modeled."},{"cited_title":"Graduate texts in mathematics: Graph theory","cited_arxiv_id":null,"evidence_quote":"Provides the graph-theoretic definitions of walks, paths, and induced subgraphs used throughout the computation-graph construction."}],"review_version":1}