Graph-Based Deterministic Polynomial Algorithm for NP Problems

Graph-Based Deterministic Polynomial Algorithm for NP Problems Changryeol Lee∗ December 2, 2025 Abstract The P vs NP problem asks whether every problem whose solution can be verified in polynomial time (NP) can also be solved in polynomial time (P). In this paper, we present a proof that P = NP, demonstrating that every NP problem can be solved deterministically in polynomial time using a graph-based algorithm. We introduce a new Computation Model that enables the simulation of a Turing machine, and show that NP problems can be simulated efficiently within this framework. By introducing the concept of a Feasible Graph, we ensure that the simulation can be performed in polynomial time, providing a direct path to resolving the P = NP question. Our result has significant implications for fields such as cryptography, optimization, and artificial intelligence, where NP-complete problems play a central role. Keywords: P=NP, NP-Complete, Time Complexity, Deterministic Simulation, Turing Machine Computation Model, Feasible Graph Contents 1 Introduction 3 2 Related Works 3 3 Preliminaries 3 3.1 ComputationTheory....................................... 4 3.2 GraphTheory........................................... 6 3.3 SummaryofNotations...................................... 6 4 Turing Machine Computation Model 8 4.1 Concept of Computation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2 Computation Walk Construction Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 DynamicComputationGraph.................................. 15 4.4 Simulate Verifier For All Certificates (EXP version) . . . . . . . . . . . . . . . . . . . . . 16 5 Feasible Graph 20 5.1 Feasible Graph on Turing Machine Computation Graph . . . . . . . . . . . . . . . . . . . 20 5.2 Feasible graph construction algortihm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.3 Type of Walks and Edges on Feasible Graph . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6 Verification of Compuation walk 35 6.1 Edge Pruning of Non-Feasible Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2 Searching For Computing-Redundant or Computing-Disjoin Edge . . . . . . . . . . . . . . 39 6.3 VerifyingCompuationwalk ................................... 43 ∗Department of Software, Yonsei University, Mirae Campus, Wonju, Republic of Korea. [email protected] 1 7 Proof of P=NP 45 7.1 Extending Footmarks of Computation Walks . . . . . . . . . . . . . . . . . . . . . . . . . 46 7.2 Polynomial Algorithm for any NP Problem(Simulation of Verifier for All Certificates) . . 48 7.3 Reduction from NP to P via Feasible Graph Simulation . . . . . . . . . . . . . . . . . . . 53 8 Implications and Discussions 54 9 Conclusion 55 A Terminology and Definitions 57 B Computation Graph Implementation 59 C Primitive Functions 59 2 1 Introduction The question of whether P equals NP remains one of the most profound open problems in theoretical computer science. It asks whether every problem whose solution can be verified in polynomial time (i.e., in NP) can also be solved in polynomial time (i.e., in P). A proof of either P = NP or P = NP would have groundbreaking consequences in fields such as cryptography, optimization, artificial intelligence, and formal verification. Despite decades of research, no polynomial-time algorithm has been discovered for any NP-complete problem, nor has it been proven that no such algorithm can exist. Several proof techniques have been proposed to address the P = NP question. Relativizing proofs use oracles to simulate problems in fixed time, but they cannot conclusively prove the relationship between P and NP, as shown by Baker, Gill, and Solovay [ 2 ]. Natural proofs, which are based on circuit complexity lower bounds, are also ineffective in offering a direct resolution to the P vs NP problem due to the assumption of the existence of one-way functions [ 10 ]. Finally, algebrizing proofs, such as those involving arithmetization, have also been shown to be insufficient for resolving the problem [1]. In this paper, we take a novel approach by introducing a new Computation Model to show that NP algorithms can be simulated deterministically. Unlike previous approaches that attempt to simulate non-deterministic Turing machines directly, our model focuses on the simulation of certifiers, showing that they can be simulated efficiently. We introduce the concept of a Feasible Graph, which guarantees that this simulation can be performed in polynomial time. This approach provides a new avenue for addressing the P = NP question, building on existing ideas while overcoming the limitations of previous techniques. The fundamental insight of this work is that, while preserving the intrinsic decision structure of the NP verifier, the verification process can be reduced to checking the existence of certain polynomially bounded computational structures, rather than exhaustively examining exponentially many certificates. This polynomial bound facilitates a complete simulation of the NP verifier within polynomial time, thus surmounting the classical exponential verification barrier and strongly suggesting P=NP. 2 Related Works The question of whether P = NP has been one of the most enduring open problems in theoretical computer science. Many researchers have attempted to resolve this question, focusing on various aspects of the NP complexity class and its relationship with P. The foundational work on NP-completeness, such as Cook’s Theorem [ 3 ] and Karp’s 21 NP-complete problems [ 8 ], established the importance of NP-complete problems in the context of polynomial-time algorithms. Several proof techniques have been proposed in an attempt to resolve P = NP , including relativizing proofs,natural proofs, and algebrizing proofs. Relativizing proofs, which involve oracles that provide fixed solutions to specific problems, have been shown to be insufficient as they can only prove results true for all possible oracles, and therefore cannot resolve P = NP [ 2 ]. Similarly, natural proofs, which are used to establish lower bounds in circuit complexity, are limited by the existence of one-way functions, making them ineffective for resolving P = NP [ 10 ]. Algebrizing proofs, such as arithmetization, have also proven ineffective for P = NP , as shown by Aaronson and Wigderson in 2008 [ 1 ]. These techniques, while useful in other areas of complexity theory, are not capable of resolving the P=NP question. Our work builds on these foundational ideas but takes a novel approach by introducing a new Computation Model, where we show that NP algorithms can be simulated deterministically. This model allows us to introduce the concept of a Feasible Graph, which ensures that the simulation can be performed in polynomial time, a technique that has not been explicitly explored in prior works. 3 Preliminaries In this section, we introduce key definitions and concepts relevant to our study, providing a rigorous mathematical framework to support our analysis. This includes essential computation-theoretic and graphtheoretic concepts, such as formal definitions of NP, verifiers, and certificates, which lay the foundation for our approach. Throughout this paper, we use function parameters exclusively for input values, while procedure parameters are annotated with directionality indicators: In denotes an input parameter (read-only), 3 Out denotes an output parameter (write-only), and In/Out denotes a parameter that is both read and modified during execution. 3.1 Computation Theory A Turing machine consists of a tape and a tape head. The tape is a sequence of cells with infinite length, each containing a symbol from a finite alphabet [ 6 , p.382]. There exists a finite set of instructions that cause the tape head to read the symbol from a cell, write a symbol into the same cell, and move left or right. The formal definition is as follows [7]: •Qis a finite non-empty set of states, •F⊆Qis the set of final states, •ϵis the blank symbol, •Γis a finite non-empty tape alphabet, •Σ⊆Γ\ {ϵ}is the set of input symbols, and •δis a transition relation defined as δ⊆((Q\F)×Γ) ×(Γ × {−1,+1} × Q), where each transition (( q, σ ) , ( σ′, d, q′ )) ∈δ indicates that when the machine is in state q and reads symbol σ, it may write symbol σ′, move the tape head in direction d, and change to state q′. With this definition, each instruction can be represented as a 5-tuple ( q, σ, σ′, d, q′ )where: q∈Q is the current state, σ∈ Γis the current tape symbol, σ′∈ Γis the symbol to write, d∈ {− 1 , +1 } is the movement direction, and q′∈Qis the next state. An execution of a Turing machine program is a sequence of such instructions, denoted as I1, I2,· · · , In , where nis the number of instructions executed. Definition 1. If a Turing machine has at least two transitions defined for the same state and input symbol, then it is called nondeterministic; otherwise, it is called deterministic [ 6 ]. We denote a deterministic Turing machine as DTM and a nondeterministic Turing machine as NTM. In a deterministic Turing machine, the transition relation δbecomes a partial function: δ: (Q\F)×Γ→Γ× {−1,+1} × Q. Definition 2. The cell index is defined as the offset from the starting cell, such that the cells to its right are assigned positive indices and those to its left are assigned negative indices. Adecision problem is a computational problem where the output is either “yes” or “no”. Such problems are typically addressed using a specific kind of Turing machine known as an acceptor. Definition 3. An acceptor Turing machine is a Turing machine that always halts in either an accepting state or a rejecting state. This is functionally equivalent to a recognizer, but the term “acceptor” emphasizes its role in deciding acceptance. The final states of an acceptor consist only of a designated accepting state qacc and rejecting state qrej. Accordingly, a decision problem is said to be decidable if there exists an acceptor Turing machine that halts on every input and correctly decides whether to accept or reject. Definition 4 (NP via Nondeterministic Turing Machine).A decision problem is in the class NP if it can be solved by a nondeterministic Turing machine within polynomial time. More formally, a language L⊆ Σ ∗ belongs to NP if and only if there exists a nondeterministic Turing machine M and a polynomial p(n)such that for every x∈Σ∗: x∈L⇐⇒ There exists a computation path of Mon input xthat accepts within p(|x|)steps. 4 Definition 5 (NP-completeness).A decision problem is NP-complete if it belongs to NP and every problem in NP can be reduced to it in polynomial time. Since every NP-complete problem is also in NP, it follows that if every problem in NP can be solved in polynomial time (i.e., if P=NP), then all NP-complete problems are also solvable in polynomial time. An equivalent characterization of NP uses the notion of an efficient certifier, capturing the verifierbased perspective of nondeterministic computation. Definition 6 (NP via Verifier and Certificate).[ 9 , pp.464] Let X be a decision problem, the set of strings on which the answer is “yes“. An algorithm Bis called an efficient certifier for Xif: 1. Bis a deterministic algorithm that runs in polynomial time; 2. Btakes two inputs, s(an instance) and t(a certificate), and outputs “yes” or “no”; 3. There exists a polynomial function p such that for every string s , we have s∈X if and only if there exists a string twith |t|⩽p(|s|)such that B(s, t) = “yes”. If there exists an efficient certifier Bfor X, then Xbelongs to the class NP. Here, the input s represents a specific problem instance (e.g., a boolean formula for 3SAT or a graph for CLIQUE), while t represents a solution candidate (also called a certificate) whose validity can be efficiently verified by B. This formulation is known as the certifier-based definition of NP. Remark 1. Note that not every string t of length at most p ( |s| )is necessarily a valid certificate for s . The verifier B may reject many strings t that do not constitute a correct certificate. The important property is the existence of at least one valid certificate t that makes B accept when s is a yes-instance. In this paper, we use the term problem instance instead of simply “instance”, and refer to the efficient certifier as the verifier throughout for consistency with standard literature. This verifier-based definition can be naturally reformulated using acceptor Turing machines: a problem belongs to NP if there exists a deterministic Turing machine that, given a certificate, verifies the solution within polynomial time and accepts if and only if the certificate is valid. Definition 7 (NP via Acceptor Verification).A language L⊆ Σ ∗ belongs to NP if there exists a deterministic acceptor Turing machine Mand a polynomial p(n)such that for every x∈Σ∗: x∈L⇐⇒ ∃t∈Σ∗with |t|⩽p(|x|)such that M(x, t)accepts within p(|x|)steps. This perspective enables a concrete method to solve NP problems: simulate the verifier on all candidate certificates of polynomially bounded length. For instance, in the canonical 3-SAT problem, a certificate t can be a Boolean assignment to the variables of a formula. The verifier is a Turing machine that evaluates the formula under the assignment encoded in t . Since the number of possible assignments grows exponentially in the number of variables, a naive brute-force approach is exponential. However, the bounded certificate length allows us to restrict our attention to certificates of length at most p(|x|)for some polynomial p. Lemma 1 (Existence of a Universal Verifier for NP).There exists a deterministic polynomial-time verifier M such that, if it can verify all certificates in polynomial time, then every NP problem can be solved in polynomial time. Proof. Since CSAT is NP-complete, there exists a polynomial-time many-one reduction from any language L∈NP to CSAT. That is, for any instance x of L , we can compute the reduction function R ( x )in polynomial time such that x∈Lif and only if R(x)∈CSAT. Let MCSAT be the verifier described in algorithm 1, which checks whether a given certificate string t over the alphabet {T, F} satisfies the Boolean formula R ( x ). By construction, MCSAT runs in polynomial time and accepts only valid Boolean assignments over {T, F}. To construct a verifier ML for L , define ML ( x, t ) := MCSAT ( R ( x ) , t ). This composite verifier ML runs in polynomial time, since both R and MCSAT do. Moreover, ML accepts ( x, t )if and only if x∈L and t is a valid certificate. Hence, we conclude that a universal verifier for all NP languages exists via reduction to MCSAT . In our framework, we simulate all such certificate candidates within a controlled computation model using a feasible graph structure. This lays the foundation for the deterministic simulation algorithm we introduce in later sections. 5 Algorithm 1 Verifier for all certificate input Input:Lis composed of two parts: problem instance and certificate, separated by a single delimiter # 1: function VerifyCertificateForAllCertificateString(L) 2: if the number of delimiters #in Lis not exactly 1then 3: return qrej 4: end if 5: Let Lc←substring of Lright of delimiter # 6: if Lcis empty or contains symbol /∈ {T,F}then 7: return qrej 8: end if 9: return VerifyCertificate(L) 10: end function 3.2 Graph Theory As our computation model is ultimately represented as a graph structure, we next introduce basic notions from graph theory that will be used to describe and analyze the structure and traversal of computation graphs. A directed graph is a pair G = ( V, E )of sets such that E⊆V×V where V is the set of vertices (or nodes)[ 5 , p.28,p.2-10]. For an edge e = ( u, v ) ∈E , an ordered pair of vertices, u is the initial vertex of e and v is the terminal vertex of e , and we denote the initial vertex as init ( e ), and the terminal vertex as term ( e ). In a directed graph, an edge e = ( u, v )is said to be an incoming edge to vertex v and an outgoing edge from vertex u . For convenience, the notation e∈G means that e is an edge of G , i.e., e∈E ( G ). The size of a graph G , denoted by ||G|| , is the number of edges, and the order of G , denoted by |G| , is the number of vertices. The degree of a vertex v is the number of edges at v , and its in-degree is the number of its incoming edges, and the out-degree is the number of its outgoing edges. A pendant edge is an edge incident to a node of degree 1. A walk of length k in graph G is a non-empty alternating sequence v0e0v1e1· · · ek−1vk of vertices and edges in a directed graph Gsuch that ei= (vi, vi+1). Since an edge has a direction on the directed graph, we can simply denote a walk of length k as e0e1· · · ek−1 where ei = ( ui, vi )and ei+1 = ( ui+1, vi+1 ), with vi = ui+1 for all i<k− 1. We refer to e0 as the initial edge (or start edge) and to ek−1 as the final edge of the walk. We also refer to v0 (i.e., init ( e )) as the initial vertex of the walk. A subwalk of a walk W = e0e1· · · ek−1 is a contiguous subsequence eiei+1 · · · ej (0 ⩽i⩽j < k)that also forms a walk. A path is a walk in which all vertices are distinct (i.e., no vertex is repeated). For an edge e = uv in G , both vertices u and v are said to be incident to the edge e [ 11 ]. For a nonempty set of edges E , we say that the subgraph ⟨E⟩ (or G [ E ]) is the subgraph induced by E if it consists of all edges in E and all vertices incident to at least one edge in E. Definition 8 (Graph Extension and Removal).Let G = ( V, E )be a graph and H⊆G be a subgraph. For an edge e∈E, define: •The extension of Hby e, denoted H+e, as the graph: H+e:= (V(H), E(H)∪ {e}). •The removal of efrom G, denoted G−e, as the graph: G−e:= (V, E \ {e}). 3.3 Summary of Notations The following table summarizes the key symbols and notations used throughout the paper. For clarity, only the most important or frequently referenced symbols are included. A more comprehensive list of technical terms and definitions is provided in appendix A. 6 Table 1: Summary of Key Symbols Symbol Description Reference G= (V, E)Computation graph with vertex set Vand edge set Esection 3.2 QSet of Turing machine states section 3.1 ΓTape alphabet section 3.1 s′Symbol to write on tape as per transition function (element of Γ) algorithm 2 sCurrent symbol read from tape (element of Γ) algorithm 2 ΣInput alphabet (Σ⊆Γ\ {ϵ}) section 3.1 ϵBlank symbol on tape section 3.1 δTransition function δ(q, σ)=(q′, σ′, d)section 3.1 p(n)Polynomial time bound for verifier section 3.1 qacc,qrej Accept / Reject states section 3.1 FSet of final states section 3.1 Vq,σ j,t Transition case at cell j, tier t, state q, symbol σsection 4 WComputation walk (sequence of edges) section 4 efFinal edge of a computation walk section 5 EfSet of final edges section 5 EiEdge slice in Gwith index i, i.e., Ei={e∈E(G)|index(e) = i}. section 4 GiSubgraph of Ginduced by Ei, i.e., Gi:= G[Ei]section 4 C(k)Step-extended component of depth k, constructed from Ef. section 5 b CSet of cover edges reachable via ceiling-adjacency from Ef. section 5 MG(Ef)Maximal step-extended component of Efin G. section 5 index(v)Cell index (tape position) of node vsection 4 tier(v)Tier (number of transitions at index(v)) section 4 state(v)Current state of computation node vsection 4 symbol(v)Current tape symbol at node vsection 4 last_state(v)Previous state at index(v)before current transition section 4 last_symbol(v)Symbol before current symbol at index(v)section 4 next_state(v)State after transition from vsection 4 output(v)Symbol written by transition from vsection 4 next_index(v)Cell index moved to after transition from vsection 4 Prec(v)Precedent transition case of node vsection 4 SuccG(v)Succedent nodes of vin graph Gsection 4 index(e) min(index(u), index(v)) for edge e= (u, v)section 4 init(e)Initial vertex of edge e= (u, v), i.e., usection 4 term(e)Terminal vertex of edge e= (u, v), i.e., vsection 4 F(W)Footmarks graph induced by walk set Wsection 4 G(i)The i-th pruned graph in the pruning sequence. section 6 WiThe i-th attempted walk selected from G(i), which is not feasible. section 6 RCritical attempted component(the union of attempted walks) up to stage i. section 6 7 4 Turing Machine Computation Model 4.1 Concept of Computation Model For each cell, we can consider the last state q⊥ and the last tape symbol σ⊥ before the current symbol written by the last instruction executed (or transition occurred) from the cell in a DTM, and also consider the number of times transitions occurred at each cell of the Turing machine. If we have the last state and the last tape symbol, then we also have the current tape symbol since by the definition of a DTM only one transition is valid and a transition produces only one output symbol. Now we can define a computation node (or vertex) as a 6-tuple, where a directed edge between them denotes a transition or an instruction of the Turing machine. Definition 9. A computation node is a 6-tuple (i, q, σ, q⊥, σ⊥, t)where •i∈Zis the cell index, •q∈Qis the current state, •σ∈Γis the current tape symbol, •q⊥∈Qis the last state of the cell, •σ⊥∈Γis the symbol before the last output(current symbol) at the current cell •t∈N∪ { 0 } is the number of transitions that have occurred at the tape cell indexed by i during the execution of the Turing machine. We denote the cell index of a node v as index ( v ), the current state as state ( v ), the current tape symbol as symbol ( v ), the last state as last_state ( v ), and the last tape symbol as last_symbol ( v )before the last transition occurred. We also denote the number of times a transition occurred at the cell of node v as tier(v), and refer to it as the tier of node v. Definition 10. Given a deterministic Turing machine, each transition δ ( q, s ) = ( q′, s′, d )is uniquely determined for any node v such that state ( v ) = q and symbol ( v ) = s . We also define the following functions associated with a computation node v: •The next state of v:next_state(v) := q′ •The output symbol of v:output(v) := s′ •The next index of v:next_index(v) := index(v) + d Definition 11. Atransition case is defined as a set of computation nodes that share the same cell index, current state, current tape symbol, and tier. We denote a transition case with tape cell index i , current state q , current symbol σ , and tier t as Vq,σ i,t . Since we are working with a deterministic Turing machine, the transition function δ is uniquely defined for each pair of current state and symbol. Therefore, once a transition case is fixed, its next state, output symbol, and next index are uniquely determined, just as in the definition of a computation node. Each transition case with tier t = 0 contains a unique node for which the last state and last symbol are undefined, as the cell has not been visited prior to this transition. Each transition case T contains |Q| × | Γ | computation nodes(excluding tier 0), that is, |T| = |Q|×| Γ | . Moreover, for each cell index and tier, there are exactly |Q|×|Γ|distinct transition cases. Definition 12. A Turing machine computation graph is a directed graph whose vertices are computation nodes. An edge exists from a node u to a node v if and only if |index ( v ) −index ( u ) | = 1 and the configuration of vis reachable from that of uby a single transition of the Turing machine. Definition 13. Acomputation walk is a sequence of edges on a computation graph which denotes a sequence of instructions. 8 −2 −1 0 +1 +2 TC: q1,s1 TC: q1,s0 TC: q0,s1 TC: q0,s0 q0, s0 q1, s1 none Cell Index: TC: q1,s1 TC: q1,s0 TC: q0,s1 TC: q0,s0 TC: q1,s1 TC: q1,s0 TC: q0,s1 TC: q0,s0 TC: q1,s1 TC: q1,s0 TC: q0,s1 TC: q0,s0 tier 0 tier 1 q0, s1 q1, s0 the last cell state and alphabet tier 2 tier 3 TC: Transition Case 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 Vq,σ i,t ×(∪s∈Γ,t′∈N0Vq′,s i+d,t′)for some i∈Zwhere 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 ( u ), i.e., index ( v ) −index ( u ). For convenience, we denote the induced subgraph G [ Ei ]by Gi , where Ei is the set of all edges with index iin G. Definition 15. The predecessor of a node v on a computation walk W is defined as the last node p ahead of von walk Wsuch that index(p) = index(v), and it is denoted as predW(v). Let v2∈Vq′,s′ i,t+1 be a computation node with tier ( v2 ) > 0, for some q′, s′ . Then for any computation walk W that contains v2 , let v1 = predW ( v2 )be its predecessor on W . By the definitions of predecessor and computation node, the state and symbol of v1 are always well-defined and identical across all such walks W . Moreover, since index ( v1 ) = index ( v2 ), all such v1 must belong to the same transition case Vq,s i,t , where q= state(v1),s= symbol(v1), and t= tier(v2)−1. This unique transition case from which a computation node v2 inherits its prior state and symbol naturally plays a fundamental role in the walk’s construction. We refer to this transition case as the precedent of v2, formally defined as follows: Definition 16. The precedent of a computation node v in G is defined as the unique transition case P satisfying the following conditions: •state(P) = last_state(v), •symbol(P) = last_symbol(v), •index(P) = index(v), •tier(P) = tier(v)−1. This is well-defined for all nodes v with tier ( v ) > 0, and is denoted by PrecG ( v ), or simply Prec ( v )when the context is clear. 9 blank symbol area ϵ ϵ blank symbol area fixed symbol area L all symbols in Γ certificate area 0 1 −1 2 · · · · · · Figure 5: Turing Machine Taple Area For Verifier 4.4 Simulate Verifier For All Certificates (EXP version) The goal of this section is to construct an algorithm that simulates the behavior of a verifier Turing machine M for all possible certificates of bounded length. This simulation must enumerate and explore all possible execution paths resulting from each candidate certificate, and check whether M accepts any of them. In doing so, we define a systematic procedure that represents this simulation as a walk over the computation graph described earlier, capturing both the structure and evolution of the verifier’s computation. We first present a naive simulation algorithm that explores all possible certificates of bounded length. This version is exponential-time due to exhaustive branching on every possible certificate symbol. Despite its inefficiency, this version is logically complete and will serve as the foundation for the optimized polynomial-time simulation in the later section. Let M = ( Q, Σ , Γ , δ, q0, qacc, qrej )be a deterministic universal verifier machine  lemma 1, e.g., for CSAT. •Q is a finite set of states; Σis the input alphabet; Γ ⊇ Σ ∪ {ϵ} is the tape alphabet, where ϵ is a fixed blank symbol. •δ:Q×Γ→Q×Γ× {−1,+1}is the transition function. •q0∈Qis the initial state; qacc, qrej ∈Qare the accepting and rejecting final states, respectively. We now describe the algorithm SimulateVerifierForAllCertificates() (algorithm 3), which simulates the verifier Turing machine M for all possible certificates of size m , given a problem instance string L . For each certificate, the machine runs in at most p ( n )steps, where n = m + |L| and p is a polynomial function. The verifier M takes as input a fixed problem instance L∈ Σfollowed by a certificate string of length at most m, both over Σ. Built-in input sanitization By design, this universal verifier M already performs comprehensive validation on its input strings: it correctly handles all possible certificate strings, including those containing delimiter symbols or other special characters. Therefore, any malformed or invalid certificate is rejected internally by M, and the verifier never behaves incorrectly or undefined on any input. This built-in sanitization ensures that when simulating M over the space of all certificate strings, we do not need to explicitly filter or preprocess certificates externally. Algorithm 3 simulates M by exhaustively enumerating all certificates of length at most m . The algorithm constructs a dynamic computation graph G representing all computation paths and deterministically simulates Mby depth-first traversal of G. This recursive simulation algorithm systematically traverses the layered graph constructed from Turing machine configurations. The input L is split into a fixed problem instance and a certificate of length m . Tier-0 nodes directly encode the tape contents, and transitions propagate across tiers as simulation unfolds. Lemma 5 (Correctness of Verifier Simulation(EXP verion)).Algorithm 3 correctly simulates the behavior of the verifier Turing Machine M for all certificates of length m on the given problem instance L . It returns Yes if and only if there exists a certificate that causes M to reach the accepting state, and it returns No if and only if there exists a certificate that causes Mto reach the rejecting state. Moreover, before termination, the computation graph G contains all configurations (nodes and transitions) that appear in any computation walk of Mon all possible certificates of length m. 16 Algorithm 3 Simulate Verifier For All Certificates (EXP version) Input:L : problem instance string ending with delimiter, m : certificate length, q0 : initial state of verifier TM 1: Σ: input alphabet, δ: transition function, F={qacc, qrej}: set of final states Output: The decision result: Yes if any certificate makes verifier accept, otherwise No 2: function SimulateVerifierForAllCertificates(L, m, q0,Σ, δ, F) 3: Let Γ←Σ∪ {ϵ}▷empty symbol is fixed as ϵ 4: Let Gbe a dynamic computation graph constructed during simulation 5: Let S←an empty dynamic array of transition cases 6: Let W←an empty list of edges 7: Let s0←L[0] ▷Problem Instance is not empty string 8: Let v0be the unique node in Vq0,s0 0,0▷v0:Initial vertex for input symbol s 9: if ProceedToNextNodes(G, v0, S, W, Γ, L, m)then 10: return Yes 11: end if 12: return No 13: end function 14: function ProceedToNextNodes(G, v, S, W, Γ, L, m, F) 15: Let i←index(v) 16: Set S[i]←the transition case containing v▷Update surface Sat ith element 17: Let i′←next_index(v) 18: if state(v)∈Fthen 19: return state(v) = qacc 20: else if S[i′]is undefined and len(L)⩽i′< len(L) + mthen ▷len(L): length of L 21: for all s′∈Γdo 22: Let S′←copy of Sand let W′←copy of W 23: Let (v, v′)←GetNextFloorEdge(v, S′, s′) 24: Append e= (v, v′)to W′and Add eto G 25: if ProceedToNextNodes(v′, S′, W′, L, m, F)then 26: return True 27: end if 28: end for 29: return False 30: else if S[i′]is undefined and not (len(L)⩽i′<len(L) + m)then ▷Fixed tape area 31: s′←L[i′]if 0⩽i′<len(L)otherwise s′←ϵ▷len(L): length of L 32: Let (v, v′)←GetNextFloorEdge(V(G), v, S, s′) 33: else 34: Let (v, v′)←GetNextEdge(V(G), v, S) 35: end if 36: Append e= (v, v′)to Wand Add eto G 37: return ProceedToNextNodes(G, v′, S, W, L, m, F) 38: end function 39: function GetNextFloorEdge(V, v, S, s′) 40: Let (i′, q′)←(next_index(v),next_state(v)) 41: Let v′←the unique node u∈Vq′,s′ i′,0 42: Return (v, v′) 43: end function 44: function GetNextEdge(V, v, S) 45: Let (i′, q′)←(next_index(v),next_state(v)) 46: Let P′←the element(transition case) in surface Swith index i′ 47: Let T′←Vq′,s′ i′,t′with s′=output(P′), t′=tier(P′)+1 48: Let v′be the node in T′such that last_symbol(v′) = symbol(P′),last_state(v′) = state(P′) 49: Return (v, v′) 50: end function 17 Proof. Let G be the computation graph constructed by algorithm 3, where each node v = ( q, i, s ) represents a verifier configuration consisting of control state q , head position i , and tape snapshot s . Let W= (v0, v1, . . . , vk)be any path in G. Then: W∈G⇐⇒ (Wis a valid computation walk of the verifier Mon input L◦y, for some certificate y∈Σm. We prove both directions separately. Soundness) We show that any computation walk W = ( v0, . . . , vk )constructed and recorded in G corresponds to a valid execution of Mon some input L◦yfor some certificate y∈Σm. We proceed by induction on the length k of the computation walk W . Note that output ( T )is the output symbol of transition for the ( state ( T ) , symbol ( T )) by construction of the dynamic computation graph where Tis a transition case on the surface. Base Case ( k = 0): The only node is v0 = ( q0, i0, s0 ), where q0 is the initial state, i0 is the head position at the beginning of execution, and s0is initialized with input Lfollowed by undefined symbols for the certificate. This configuration corresponds to the correct initial configuration of M , so the walk of length 0 is trivially valid. Inductive Step: Assume all computation walks of length ⩽k recorded in G correspond to valid executions of M. Let W = ( v0, . . . , vk, vk+1 )be a walk extended in G by some recursive call. There are four cases depending on whether the surface transition from vkto vk+1 is deterministic or nondeterministic: Given node v with tape head at position i = index ( v ), define i′ = next_index ( v )as the next tape cell to visit and q′ = next_index ( v )as the next state of the Turing Machine. Consider recursive call ProceedToNextNodes() with depth k. • Case 1(Deterministic transition with first visiting the cell at fixed input region): If S[i′]is undefined but i′lies in the fixed input region or empty symbol region (i.e., i′<len(L)or i′⩾len ( L ) + m ), the algorithm deterministically sets s′ = L [ i′ ](or ϵ for empty cells), computes the unique next node v′ via GetNextFloorEdge(), and proceeds recursively without branching. Thus, node vk+1 is the computation node v′ for tier 0, symbol L [ i′ ](or ϵ for empty cells) and the current state. • Case 2 (Deterministic transition with re-visiting the cell): If S [ i′ ]is defined (the tape symbol at i′ is known from prior steps), then the next node v′ is deterministically computed via GetNextEdge() using transition case S [ i′ ]on surface S , and the simulation proceeds recursively without branching. Thus, node vk+1 is the computation node v′ for symbol output ( S [ i′ ]) and the current state with precedent S[i′]. • Case 3 (Nondeterministic certificate branching with first visiting the cell at certificate input region): If S [ i′ ]is undefined and i′ lies in the certificate region (i.e., len ( L ) ⩽ i′<len ( L ) + m ), the algorithm iterates over all possible symbols s′∈ Γfor this cell. For each such s′ , GetNextFloorEdge() computes the next node v′ and recursively calls ProceedToNextNodes()( v′, S′, W′, L, m )with updated surface S′ including S′ [ i′ ]where S′ is copy of surface S and W′ is a copy of the walk W with the edge ( v, v′ )appended, simulating the nondeterministic branches. Thus, node vk+1 is the computation node for all possible certificate symbols and tier 0without precedent transition cases. • Case 4 (Final state): vk is a halting configuration with qk∈F = {qacc, qrej} . No further transitions are made, and vk becomes the endpoint of W , returning True for the accepting state or False for the rejecting state. If it returns True , all recursive calls return as well, and when the initial ProceedToNextNodes() call returns, it outputs Yes. In all cases, S [ i′ ]is updated with the current transition case, ensuring that output ( S [ i′ ]) is the correct tape symbol determined by state(S[i′]) and symbol(S[i′]). Moreover, vk+1 is a valid next node of vk according to M ’s transition semantics. By the inductive hypothesis, the subwalk ( v0, . . . , vk )is valid, and the surface tracks the latest transition case, preserving 18 both the preceding state and the symbol before overwritten as a current symbol. Furthermore, the edge ( vk, vk+1 )is appended to the computation walk W or its copy W′ , and also added to the graph G . Therefore, Wis a valid computation walk of length k+ 1. Finally, the algorithm outputs Yes only if there exists a valid computation walk whose final node represents an accepting state. This guarantees that any Yes returned is always correct, completing the proof—that is, soundness holds. Completeness) Suppose, for contradiction, that there exists a maximal computation walk W such that the next transition exists of the final node vk of W at the return of the recursive call, or vk exists but the (vk−1, vk)is not in G. W= (v0, v1, . . . , vk) of M on input L◦y for some y∈ Σ m , such that W⊆ G , i.e., the simulation algorithm failed to construct Winto G. First, consider when there exists transtion at the configuration of final node, but there in no computation node for it in W . For the Case 1,2 in the soundness proof, there can be only one configuration due to the DTM and the computatin node is always computed since the state of the node is not the final state, and appendded at the end of W , which contradicts the maximality of W . For the case 3 in the souncess proof, since multiple symbol is possible, there can be | Γ | computation node after the final transition each represents each symbol, but for all symbols computation node computed and added to W (or W′ ). Again, this contradicts the maximality of W . Second, consider ( vk−1, vk )exists but it is not in G .But the edge is always added to Gas soon as it is added to W, which is a contradiction. In all cases, vkmust have been generated and added to G, contradicting our assumption. Thus, every valid computation walk is fully constructed and the edge should be contained in G. Finally, since the algorithm explores all possible valid computation walks, if there is no accepting state at the end of any computation walk, then there are no possible transitions that reach an accepting state. This guarantees that if the algorithm returns No , it is correct, completing the proof—i.e., completeness holds. Note on the Role of Tier. Although the current simulation algorithm does not rely on the tier structure for its correctness or completeness, we maintain it as part of the computation graph definition. This is because the tier structure becomes crucial in the subsequent section, where we design a polynomialtime simulation algorithm that exploits the layered nature of computation to achieve efficiency. In particular, tiers will help organize configurations by time steps and enable bottom-up reasoning across the graph. Lemma 6 (Polynomial Bounds of Footmarks of Computation Walks of All NP Certificates).Let M = ( Q, Γ , δ, q0, F )be a verifier Turing machine for an NP problem with input of size n , where F = {qacc, qrej} . Suppose that M returns Yes or No to any problem instance L and all certificates of length at most m, and runs in time at most p(n), where n=|L|+mfor some polynomial p. Then, the computation graph constructed by simulating all valid computations of M on all such certificates (as in algorithm 3) has both width and height bounded by O ( p ( n )). In particular, the order(the total number of vertices) is O(p(n)2)and the size(the total number of edges) in the graph is O(p(n)3). Proof. We assume p ( n )bounds both the certificate length and the verifier’s running time. Since the verifier halts within p ( n )steps, and by the definition of tier (see definition 9), each transition increases the tier by at most one, the maximum tier of any node is at most p ( n ). Thus, the height of the computation graph is O(p(n)). Next, since the verifier uses at most p ( n )cells during its execution, the reachable tape region is bounded. Each configuration is determined by the current state, the head position (at most p ( n )possibilities), and the content of at most p ( n )tape cells. So the number of distinct configurations at each tier is bounded by O(p(n)), and this gives the width of the graph. Regarding the outdegree of each node: While an individual transition defined by δ is constant, because the simulation considers all possible certificates, at each node there may be up to O ( p ( n )) possible next nodes, since the height of the computation graph is O ( p ( n )) and all edges only connect nodes with 19 consecutive tape indices (index difference exactly ± 1), which means the outdegree of a node is bounded by O(p(n)). Therefore, with O ( p ( n ) 2 )nodes each having O ( p ( n )) outgoing edges, the total number of edges is bounded by O(p(n)3). Polynomial Bound and Its Consequence. By Lemma 6, the computation graph of the verifier Turing machine for all certificates has polynomially bounded width and height, and hence polynomial size overall. This polynomial bound is a crucial structural property that enables the construction of a simulation algorithm with polynomial-time complexity, as detailed in the subsequent section. As a consequence, we will later demonstrate that every language in NP can be decided by a deterministic polynomial-time algorithm, ultimately establishing P=NP. 5 Feasible Graph To transition from the exponential-time simulation algorithm introduced in algorithm 3 to a polynomialtime approach, this section introduces a refined graph structure called the feasible graph. Building on the computation model established in section 4.1, we now develop additional structural tools tailored for efficient analysis. These include new notions such as step-adjacent components,ceilingand floor-edges,step-extended components, and feasible obsolete walks. These concepts capture localized propagation and interaction patterns in the computation graph, and they form the foundation for designing a polynomial-time simulation in the subsequent section. For completeness, we continue to rely on previously defined notions such as computation nodes, tiers, precedents, and folding nodes, as introduced in the earlier sections. 5.1 Feasible Graph on Turing Machine Computation Graph In this subsection, we introduce key concepts and terminology related to the feasible graph. We begin by defining essential terms and the notion of step-extended components. Using these, we then formally define the feasible graph. Finally, we describe various types of walks and edges defined on the feasible graph that will be instrumental in the subsequent analysis. Definition 26. Let Wbe a set of computation walks. An edge e∈Wis called a ceiling edge if it has no successor edge in the walk W. An edge (u, v)is called a floor edge if it has no predecessor edge in the walk W. A floor edge corresponds to the first edge at a given edge index, and a ceiling edge corresponds to the last edge at a given edge index within a walk. Thus, we refer to floor or ceiling edges by their edge index, and the i-th ceiling edge of Wrefers to the unique ceiling edge with edge index iin the walk W. Lemma 7. An edge e= (u, v)is a floor edge if and only if tier(v)=0for any computation walk. Proof. We prove both directions of the equivalence. (If direction) Suppose, for contradiction, that e is not a floor edge. Then there exists e′ which is a predecessor of e in some walk W by definition of floor edge. Let s be the start node of W . Recall that any computation walk is a path, which means all computation node is distinct. And there also exists node v′ incident to e′ with index ( v′ ) = index ( v ) , tier ( v′ ) < tier ( v )other than v in the subwalk from s to u . Since tier ( v ) > tier ( v′ ), tier ( v ) > 0, even if tier ( v′ ) = 0. This contradicts the assumption that tier(v)=0. (Only if direction) Suppose, for contradiction, that tier ( v ) > 0. We will show that e = ( u, v )cannot be a floor edge. Since tier ( v ) > 0, there exists a node v′ such that index ( v′ ) = index ( v )and tier ( v′ ) = 0; that is, v′ represents the first visit to the tape cell indexed by index(v). Let sand tdenote the start and final nodes of the walk W, respectively. We consider two cases based on the direction of the edge ein W: Case 1: eis directed toward the origin. Then the walk W can be decomposed into three subwalks: W1 — from s to v′ , W2 — from v′ to u , W3 — from u to t . In W2 , there must exist an edge e′ with index ( e′ ) = index ( e )that precedes e in W 20 due to |index ( u ) |> index ( v′ ), making e′ a predecessor of e —contradicting the assumption that e is a floor edge. Case 2: eis directed away from the origin. Then the walk W can again be decomposed into three subwalks: W1 — from s to v′ , W2 — from v′ to u , W3 — from u to t . In W2 , there must again exist an edge e′ with index ( e′ ) = index ( e )due to |index ( u ) < index ( v′ ) | that appears before e in W , serving as a predecessor—again contradicting the assumption. In both cases, emust have a predecessor with the same index, so it cannot be a floor edge. e v u e′ v′ u′ v (a) Floor edge case direction toward origin e v u e′ v′ u′ v W2 (b) Floor edge case direction away from origin Remark 2 (Global Character of Floor Edges).Although the notion of a floor edge is defined locally with respect to a computation walk, lemma 7 shows that an edge ( u, v )is a floor edge in any computation walk if and only if tier ( v ) = 0. Therefore, the classification of floor edges is globally consistent and independent of any particular walk. This global characterization enables reasoning about floor edges without reference to specific walks. Definition 27 (Ex-Pendant Edge).Let e∈E be an edge with index i in the computation graph G = ( V, E ). We say that e is left-pendant if there exists no edge in E adjacent to e with index i− 1, and the node of e with index i is not a folding node. We say that e is right-pendant if there exists no edge adjacent to e with index i + 1, and the node of e with index i + 1 is not a folding node. If e is either left-pendant or right-pendant, we say that eis ex-pendant. Lemma 8. Let e be an edge incident to a source or sink node in the computation graph. Then e is an ex-pendant edge, where a source node has only outgoing edges and a sink node has only incoming edges. Proof. Case 1: Suppose vis a source node. Then v has only outgoing edges. By the properties of the DTM, all outgoing edges from v must have the same direction, implying they all have the same index. Therefore, there exists no edge adjacent to any such edge with index i− 1or i + 1. Thus, each edge is either left-pendant or right-pendant, and hence ex-pendant. Case 2: Suppose vis a sink node. Let e = ( u, v )be an incoming edge to v . We claim that for any such edge e , the predecessor edge predW ( e ) in any computation walk Wmust have the opposite direction to e. Suppose, for the sake of contradiction, that predW(e)has the same direction as e. Let predW(e)=(u′, v′), where v′= predW(v). Let i= index(u). Then the index difference satisfies: |index(v′)−i|>0,and index(u)−i= 0, which means there exists a path from v′to uthat has the opposite direction of e′in W. Since there is a path from v′ to u , this path must include some edge e′′ with index ( e′′ ) = index ( e′ ), contradicting the assumption that e′is a predecessor of ein W. Therefore, predW(e)must have the opposite direction to e. Now suppose v has two incoming edges f and f′ with opposite directions. Then there exist two walks Wf and Wf′ containing f and f′ , respectively. By the previous claim, predWf ( f )and predWf′ ( f′ )also 21 have opposite directions, implying that Prec ( v )contains nodes from both directions. This contradicts the definition of Prec(v), where all precedent nodes must have the same direction (see lemma 2). Thus, every edge incident to a sink node must be either leftor right-pendant, and therefore expendant. Definition 28 (Ceiling-Adjacent Edge).Given an edge e = ( v, w )and set Ef in a computation graph G , another edge f= (u, v′)is said to be ceiling-adjacent to etoward Efif one of the following holds: •fis adjacent to e, and index(f) = index(e)−dir(e); •fis adjacent to an edge e′such that there exists a sequence of edges e0, e1, . . . , enin Gsatisfying: –e0=e,en=e′; –either e0in Efor init(e0)is a folding node; –for all 0⩽i<n,ei+1 ∈PrecG(ei); –every node v′′ incident to ei(for 0< i < n) with index(v′′) = index(v)is a folding node; –v′is a non-folding node. u f e=e0 e′ =e6 v v′ w e1 e2 e3 e4 e5 (a) Ceiling-adjacent edge(e:folding edge) u f e=e0 e′ =e5 v v′ w e1 e2 e3 e4 (b) Ceiling-adjacent edge(e∈Ef) If the context is clear, we simply say that eis ceiling-adjacent to e. Note: The final edge, e∈Ef may have two distinct ceiling-adjacent edges with index ( f ) = index ( e ) ± 1. For non final edges, the ceiling-adjacent edge fsatisfies index(f) = index(e)−dir(e). Lemma 9 (Characterization of Ceiling Edges).Let e be an edge in a computation walk W in a computation graph G , where ef is the final edge and Ef = {ef} . Then, an edge e in W is a ceiling edge if and only if it is ceiling-adjacent to another ceiling edge ec toward Ef such that |index ( ef ) −index ( ec ) |< |index ( ef ) −index ( e ) | , in other words, it is ceiling-adjacent to another ceiling edge ec that is closer to the final edge efthan e. Proof. Let d= dir(ef)be the direction of the walk W. We prove the claim in two parts, depending on the sign of d·(index(ef)−index(e)). •Case 1: d·(index(ef)−index(e)) ⩾0. Let ( ck, ci+d,· · · , cm−d, cm )denote the subsequence of W , where index ( cj ) = j, ck = e , and cm = ef is the final edge of W. Suppose that cjis ceiling-adjacent to cj+dfor all jin the following range: –If d > 0, then for all jsuch that k⩽j < m; –If d < 0, then for all jsuch that k⩾j > m. We proceed by induction on |m−i|, the number of steps from cito cm. Base case ( m = i ): Then ci = cm = ef . Since term ( cm )has no outgoing edge in W , we have SuccW(ef) = ∅, and thus ciis trivially a ceiling edge. Inductive Hypothesis: Assume that the ceiling edge cj=ci+dsatisfies: 22 1. cjis a ceiling edge; 2. every edge fin the subwalk Wjfrom cjto cmsatisfies d·(index(f)−index(cj)) ⩾0. Inductive Step: We now show that cialso satisfies the above conditions. Let ci+d be the next ceiling edge after ci in W . Since W is a computation walk, ci is ahead of ci+d in W. Since ci is ceiling-adjacent to ci+d , we consider two cases based on the type of adjacency between ci and ci+d: – (a) Direct adjacency: If ci is directly adjacent to ci+d and both involve non-folding nodes, then their indices differ by ± 1, and ci has no successors in W . Therefore, ci is a ceiling edge, and Wi+dcontains no edge fsuch that d·(index(f)−index(ci)) <0. – (b) Indirect adjacency via folding edges: In this case, ci is not directly adjacent to ci+d , but there exists a sequence of folding edges from ci to an edge adjacent to ci+d (as per definition 28). Suppose, for contradiction, that there exists a successor edge ( x, y )of ci = ( u, v )in a subwalk from cito ci+d. Then: -index(x) = index(v)and tier(x)>tier(v) -index(u) = index(y)and tier(y)>tier(u)+1 (by the definition of successor; see definition 15) However, by the definition of ceiling-adjacent edge, all nodes with index ( v )are folding nodes, which implies there is no edge directed toward any node with index ( u )(See lemma 3). This contradicts the assumption that index ( u ) = index ( y )with tier ( y ) >tier ( u ) + 1. Therefore, there is no successor in the subwalk Wi+d , since by the inductive hypothesis, all edges f∈Wi+d satisfy d·(index(f)−index(ci+d)) ⩾0. Therefore, ci is a ceiling edge of W , and every edge f∈Wi satisfies d· ( index ( f ) −index ( ci )) ⩾ 0. In both cases, ci is the unique ceiling edge with edge index i satisfying the desired property, and all edges f∈Wi satisfy d· ( index ( f ) −index ( ci )) ⩾ 0. Since each index admits at most one ceiling edge, any ceiling edge must be ceiling-adjacent to another ceiling edge in the walk, and thus the "only if" condition is satisfied. Therefore, by induction, the stated properties hold for all indices iin the given range. • Case 2: d· ( index ( ef ) −index ( e )) < 0.Let cm+d be the edge ceiling-adjacent to ef = cm . Then, by a similar argument as in Case 1 (specifically the (b) case where d· ( index ( ef ) −index ( e )) > 0), cm+dis the unique ceiling edge with edge index m+d. Let W′ be the reversed subwalk from the start of W up to the edge cm+d . Apply the same inductive structure as in Case 1, using −d as the direction. The same reasoning applies symmetrically, ensuring that the ceiling-edge property is preserved under reversed direction. Conclusion: An edge in the computation walk W is a ceiling edge if and only if it is ceiling-adjacent to another ceiling edge that is closer to the final edge ef . This characterization holds regardless of whether the walk proceeds in increasing or decreasing index order. This lemma serves to propagate the ceiling edge property backwards along a computation walk via ceiling-adjacency. While floor edge is globally well-defined within the graph structure, independent of any local walk or surface assignment, ceiling edge is solely dependent to computation walk that belongs to, since the same edge can be ceiling edge or not depends on the walk. Thus, we require a graph-theoretic notion of ceiling edge that holds globally as well, rather than being dependent on a particular walk. To formulate this, we introduce a family of edges that play a symmetric role to floor edges in a computation graph no in a walk. Definition 29 (Cover Edge).Let G be a computation graph, and let Ef be the set of final edges of the computation walks. An edge e∈E ( G )is called a cover edge with respect to Ef if there exists a finite sequence of edges (c0, c1, . . . , ck)such that: 23 •c0=e; •ck∈Ef; •for every j= 0, . . . , k −1, edge cjis ceiling-adjacent to cj+1 toward Ef. The set of all such edges is denoted by b C. We refer the sequnce (c0, c1,· · · ck)to a cover edge chain. As a direct consequence of lemma 9, every ceiling edge in a computation walk is necessarily a cover edge under the above definition. Lemma 10 (Ceiling Edges are Cover Edges).Let Wf be a set of computation walks in a computation graph G , and let Ef be the set of final edges of all walks in Wf . Let Cf denote the set of ceiling edges that appear in walks from Wf. Then Cf⊆b C, where b Cis the set of cover edges of Gwith respect to Ef, as defined in definition 29. Proof. Let H′ be a supergraph of a graph H , meaning that H′ contains all vertices and edges of H . First, consider any graph Hand its supergraph H′. Then the following properties hold: •If eis adjacent to fin H, then eis also adjacent to fin H′. •If f∈PrecH(e), then f∈PrecH′(e). • If v is a folding node in H , then v is also a folding node in H′ , since all outgoing edges from v have the same direction due to the deterministic transition mechanism (DTM). It follows that if f is ceiling-adjacent to e in H , then f is also ceiling-adjacent to e in any supergraph H′ of H. Now let W = ( e0, . . . , ek )be any walk in Wf , and let c = ei be a ceiling edge in W for some i<k , with ek∈Ef. By the definition of a ceiling edge, there exists a subsequence ( ei, ei+1, . . . , ek )of ceiling edges in W such that for each jwith i⩽j < k, the edge ejis ceiling-adjacent to ej+1. Since all ceiling-adjacency relations are preserved in G , and since ek∈Ef⊆b C (by initialization of the cover set), and cover edges are closed under backward ceiling-adjacency from Ef , it follows inductively that c=ei∈b C. Therefore, every ceiling edge c∈Cfis also in b C. With the notions of floor and cover edges in place, we now define the following concept of a step-pendant edge, which includes vertical pendant behavior within the graph. Definition 30 (Step-Pendant Edge).Let G be a subgraph of the footmarks graph of a set of computation walks, and let Efbe a subset of final edges of walks in W. • An edge e is said to be step-adjacent to an edge f if and only if either e is adjacent to f , or e∈SuccG(f), or e∈PrecG(f)(See definition 16) •An edge eis a step-pendant edge if it satisfies one of the following: –eis an ex-pendant edge (see definition 27), –PrecG(e) = ∅,tier(v)>0(eis non-floor edge in any walk, see lemma 7); –SuccG(e) = ∅and eis not a cover edge with respect to Ef(see definition 29). To define the key notion of a feasible graph as a residual component obtained from another, we first introduce the concept of a step-extended component based on the above notion of step-pendant edges. Definition 31 (Step-Extended Component).Given a graph G and a set of edges ER , the step-extended component of ERis defined recursively as follows: Let C(0) =ER. For each n⩾0, define C(n+1) to consist of all edges e /∈C(n)such that: (i) eis step-adjacent to some edge in C(n), and (ii) eis a step-pendant edge in the subgraph G−C(n). 24 This process terminates when no such edges exist. The final set C(k) is called the maximal stepextended component and is denoted by MG(ER). Now, we define the feasible graph. Definition 32 (Feasible Graph).Let W be a set of walks in a computation graph G , and let GF be the subgraph of the footmarks graph induced by W . Let EFINAL and EINITIAL denote the sets of all final and initial edges of the walks in Wrespectively. Given a subset Ef⊆EFINAL, and let V0:= {init(e)|e∈EINITIAL}, define ER:= {e∈E(GF)|eis ex-pendant, e /∈Ef∪EINITIAL}. The feasible graph Gfeasible is then defined by removing from GF: •all edges in the maximal step-extended component MGF(ER), and •all isolated (degree-0) vertices I(GF), i.e., Gfeasible := GF\MGF(ER)\I(GF). Here, M GF ( ER )denotes the maximal step-extended component of ER in GF as defined above, and I(GF)is the set of isolated vertices in GF. We refer to Gfeasible as the feasible graph of G with respect to Ef and V0 . When we refer to a feasible graph without specifying Ef , we mean one defined with respect to some (unspecified) subset Ef⊆EFINAL . With notion of ceiling-adjacent edge, the following notion of adjanceny also used to contruct feasible graph algorithmically. Definition 33 (Index-Adjacent Edge).Given a subgraph G of the footmarks of W , let Vf be the set of final vertices of the walks in W , and let V0 be the set of initial vertices of the walks in W . Let Ei be an edge slice(indexed set of edges) in Gwith index i, i.e., Ei={e∈E|index(e) = i}. Given a computation graph G and edge index i , an edge f = ( u, v )is said to be index-adjacent to edge slice Eiif it satisfies at least one of the following conditions: •fis adjacent to an edge in Ei; •index(v) = iand (vis a folding node or f∈Efor v∈V0) 5.2 Feasible graph construction algortihm We present the algorithm ComputeFeasibleGraph(), which constructs a feasible graph from a given computation graph G , a set of start vertices V0 , and a set of particular final edges Ef . Here, G is intended to be a subgraph of the footmarks graph corresponding to computation walks from an already simulated deterministic machine, a concept that will be formally introduced in later sections. The output graph is proven to satisfy the conditions of a feasible graph as defined in definition 32. This algorithm uses a subroutine Compute() to compute cover edges for each walk, which is invoked once at the beginning. We first present this subroutine and prove its correctness and time complexity. Then, we present the main algorithm and verify its correctness and complexity. The main algorithm proceeds as follows. The following subalgorithm computes the cover edges dfined in definition 29. Sublemma 1 (Correctness of Computing Cover Edges).Given a subgraph G of the footmark graph of walks W , and the subset Ef of final edges of the walks, the set C returned by ComputeCoverEdges() in algorithm 5 contains an edge if and only if it is a cover edge of Wwith respect to Ef. Proof. Let the final edge efbe trivially included as the base case at line 2. Define c0=ef. (Soundness): Assume as an induction hypothesis (IH) that the edges c0, c1, . . . , ck have been correctly appended to the set C by the algorithm, and that each ci+1 is ceiling-adjacent to ci , and is a cover edge. Since all ceiling-adjacent edges are added to Q , ck is also added to Q . Consider the execution step when ck is retrieved from Q . If ck+1 is already in C , then the proposition holds trivially. By the algorithm, 25 Note. The notion of a feasible walk plays a central role in both pruning the computation graph and verifying the validity of computation paths. As we progressively remove infeasible portions of the graph, feasible walks serve as the structural backbone that preserves all valid computation paths. This makes them essential in the design of our deterministic simulation of the verifier. The following lemma shows that the feasible graph always preserves any walks ending with the given final edges. Lemma 15. Given a subgraph Gf representing the footmarks of walks, a set of initial vertices V0 of all walks, and a set of edges Ef\EFINAL, where EFINAL is the set of final edges of all walks in W, let H be the feasible graph constructed by Algorithm 4 from Gf with respect to Ef and V0 . Then, all edges of any walk whose final edge belongs to Efare contained in H. In other words, any walk in Gf whose final edge belongs to Ef is always a feasible walk for Ef in the feasible graph with respect to Efand V0. Proof. Let Wf be a walk such that all its edges are in Gf and its final edge belongs to Ef . Let b C be the cover edge set with respect to Ef, computed by ComputeCoverEdge() (see sublemma 1). By Lemma 10, all ceiling edges of walks whose final edge is in Ef are included in the cover edge set. Hence, all ceiling edges of Wfbelong to b C. Let H(k) denote the feasible graph after the k -th execution of SweepEdges(), with H(0) = G . For example, after one iteration of the while loop, we have H(2). Assume for contradiction that there exists an edge e∈E(Wf)such that e /∈H. Then, there exists a minimum k such that e∈H(k−1) but e /∈H(k) . Thus, during the k -th execution, e must have failed to be added to either the inclusion set I in StepUpEdges(), or to the set I′ in StepDownEdges(). Let H′be the intermediate graph being constructed during the k-th execution of SweepEdges(). Suppose the index i (minimum or maximum, depending on direction) is the current index of the edge sweep. Then e is the first edge at index i that fails to be added. By assumption, all edges at earlier indices were added to H′. Case 1: eis not added to Iin StepUpEdges() Since Wf is a walk, the only possible ex-pendant edges are the initial and final edge. Otherwise, e must be a non-ex-pendant edge. •Non-Ex-Pendant Edge – Floor edge: Let Q be the queue with all floor edges at line line 40. Since all edges adjacent to e in Wf were added earlier(or e is folding edge), e must be included in Q and added to I , which is a contradiction. – Non-floor edge: Let ( e0, e1, . . . , em )be the sequence of edges in Wf such that e0 is a floor edge, em is a ceiling edge, and ei+1 is a successor of ei in Wf . Let ej be the first edge such that ej−1∈I but ej/∈I . Then ej is a succedent edge of ej−1 and is enqueued to Q at line 47. - If ej is a folding edge, it is also added via line line 46. - If ej is non-folding, then it is adjacent to an edge in H′and must be added via lines 46. In both cases, ejmust be added, a contradiction. •Ex-Pendant Edge By Definition 33, the index-adjacent set includes both initial and final edges. All such edges are added to Iat line 46. – Start Edge: Even if ehas no adjacent edge, it is index-adjacent and therefore belongs to Q and is added to I. – Final Edge: Since e∈Ef , it is included because it is either directly added as a floor edge or its predecessor edge f in Wf is added to I and Q (since a predecessor edge is always assigned to another case). Moreover, e is index-adjacent to previously scanned edges, so it is added as well. In either case, we contradict the assumption that ewas not added to I. 32 Thus, all edges of Wfare added to I. Case 2: eis added to Ibut not added to I′ Let ebe the first edge in Wfnot added to I′. We again consider two subcases: •Non-Ceiling Edge: Let ( e0, e1, . . . , em )be the sequence of edges such that e0 is a ceiling edge, em is a floor edge, and ei+1 is a predecessor of ei in Wf . Let ej be the first edge such that ej−1∈I′ but ej/∈I′ . Then ej is a precedent of ej−1and must be enqueued at line 33, and eventually added to I′, a contradiction. •Ceiling Edge: Since e is a ceiling edge of a walk ending in Ef , it belongs to the cover edge set b C and is added to I′at line 28, a contradiction. In both cases, emust be in I′and thus added to H′. In all cases, we reach a contradiction. Therefore, all edges of any feasible walk must belong to the graph H, and all ceiling edges of feasible walks must be included in the cover edge set C. Definition 36 (Bottom Orphaned Edge).Let ( e0, e1, . . . , ek )be a finite sequence of edges in a computation graph such that: •e0is an orphaned edge, •for all 0⩽i<k,ei+1 ∈Prec(ei), and there exists no edge ek+1 such that ek+1 ∈Prec(ek). Then, we call ekabottom orphaned edge. Since each precedent edge strictly decreases the tier of the computation node it leads to, there is no possibility of cycles formed by following precedent edges. Therefore, by repeatedly following precedent edges starting from any orphaned edge, we must eventually reach a bottom orphaned edge that has no precedent edge. Sublemma 4. Let G be a feasible graph of footmarks of walks GU . Then any orphaned edge is not a floor 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 Wthat belongs to GUbut not to the feasible graph G. Therefore, there exists a walk W′ in G that was merged into W and from which W was splitted not after the edge e during the construction of G . Otherwise, the edge e would have been removed during the construction of the feasible graph, as it would become an ex-pendant edge. Let e′ be the last splitting edge in W not after e . If e′ = e , then prevW ( e )is also an orphaned edge, contradicting the assumption that eis a first orphaned edge. Thus, e = e′ = ( u, v ). Let v0 be the initial node of W′ . Since W′ is in G , and e = ( u, v )is a splitting edge, there exists a subwalk Wuof W′from v0to u. Then, the walk v0→u→v exists in G , meaning W′′ = v0→u→v is a walk in G that includes e . Note that a transition to a tier-0 node represents a first visit to a tape cell, which necessarily forms a computation walk. Therefore, W′′ must be a computation walk. But this implies that e is not an orphaned edge — a contradiction. Therefore, no bottom orphaned edge can be a floor edge. Lemma 16. Let G be a feasible subgraph of footmarks of walks W , and let W∈ W be an orphaned walk. Then there exist at least two distinct walks W′, W′′ ∈ W \ {W} such that each of W′ and W′′ is either a feasible or obsolete walk. Proof. Suppose, for the sake of contradiction, that Wis the only walk in Wthat is feasible or obsolete. 33 e v0 W u v W′ Wu Figure 8: No Floor Orphaned Edge ep e f e′ f′ p fp (a) Existence Two Distinct Walks for Orphaned Edge Case 1 ep e f e′ fp u v vp up e′ p e′′ p (b) Existence Two Distinct Walks for Orphaned Edge Case 2.2 We consider two possible cases regarding the edges of W: Case 1: There is no orphaned edge e such that e∈SuccG ( ep )for any edge in ep∈W . Let e be the first orphaned edge encountered along W , i.e., the orphaned edge incident to the first node of W that is incident to any orphaned edge. Assume e is a bottom orphaned edge. By the definition of a bottom orphaned edge, unless e is a floor edge or some edge ep∈Prec ( e )belongs to W , no edge in Prec ( e )can be orphaned. If e is a floor edge, then by sublemma 4, e cannot be an orphaned edge, leading to a contradiction. If ep∈W , then e must belong to the succedent of ep , which again contradicts our assumption that no orphaned edge is in the succedent of W. Case 2: There exists at least one orphaned edge e∈W that belongs to the succedent of another edge ep∈W . Let e be the first such orphaned edge encountered in W , and let f∈Prev ( e ). Let e′ p be the bottom orphaned edge in the precedent chain of e. Since floor edges cannot be orphaned by sublemma 4, e′ p is not a floor edge. Then there exists e′′ p∈Prec ( e′ )such that e′′ p∈W . But then e′ p∈Succ ( e′′ p ), so e would not be the first orphaned edge in the succedent of an edge of W — a contradiction unless e = e′ p . Therefore, e is itself a bottom orphaned edge. Now we consider two subcases for f: Subcase 2.1: f is an orphaned edge. Let f′ be the bottom orphaned edge in the precedent chain of f . By the definition of a bottom orphaned edge, either f′ is a floor edge (which is impossible by sublemma 4) or some f′′ ∈Prec ( f′ )must belong to W . But then f′′ would be the first edge of W whose succedent includes an orphaned edge, contradicting the assumption that eis the first such edge. Subcase 2.2:Suppose f is a non-orphaned edge and therefore belongs to a feasible or obsolete walk. Since e= (u, v)is a bottom orphaned edge, ep= (vp, up)∈Prec(e)be an edge on W. Let e′ be the next edge of f in W . Since e′ and e share the same predecessor ep and originate from the same node u , this implies that f has two distinct next edges: e and e′ . This contradicts the determinism of the computation unless e = e′ . However, if e = e′ , then e must belong to W , which contradicts the assumption that eis an orphaned edge. In all cases, we reach a contradiction. Therefore, there must exist at least two other walks W′, W′′ ∈ W \ {W}that are either feasible or obsolete. 34 6 Verification of Compuation walk In this section, we describe an algorithm for verifying whether there exists a computation walk ending at a specific edge in a given computation graph. This is achieved using the notion of a feasible graph, which filters out irrelevant or obsolete parts of the original graph while preserving the existence of a feasible computation walk. Our approach consists of three main stages, organized into the following subsections: • Pruning of Infeasible Edges. In the first step, we remove merging edges if there exists more than one obsolete or feasible walk in the graph. In other words, we prune merging edges. • Identification of Obsolete Walks. In the second step, we iteratively prune the graph until the remaining subgraph contains at most one feasible or obsolete walk. • Verification through Edge Elimination. Finally, we systematically eliminate redundant or obsolete edges one by one. At each step, we ensure that a feasible computation walk still exists in the pruned graph, ultimately confirming whether the target edge lies on any such walk. Throughout the process, if we find a feasible walk, we stop the procedure. The combination of these three procedures enables us to efficiently verify the existence of a computation walk that ends at a specific edge, while preserving the correctness and feasibility of the walk structure. 6.1 Edge Pruning of Non-Feasible Walks This algorithm aims to prune a single edge from a given walk within a feasible graph, while ensuring that at least one feasible or obsolete walk remains in the resulting graph. The procedure PruneWalk() performs the pruning by identifying a removable edge and updating the feasible graph accordingly. The subroutine FindFirstMergingEdgeOrFinalEdge() locates the appropriate edge to be removed—either the first merging edge or, if none exists, the final edge of the walk. The AddFinalEdgesOfObsoleteWalks() procedure guarantees that the remaining obsolete walks are preserved in the updated feasible graph, even after pruning. Note: In this section, the final edge of a feasible walk does not necessarily coincide with the final edge of the current feasible graph. Rather, each feasible walk is defined with respect to a final edge of the input graph. Additionally, the final edge set of the feasible graph computed in this procedure corresponds to those edges of the input graph that have been identified as obsolete. Definition 37 (Extended Obsolete Edge).Let W be an obsolete walk and let G be the current feasible graph. An edge eof Wis called the extended obsolete edge of Wif it satisfies the following conditions: 1. e is the earliest edge of W with respect to the order of appearance in W that does not belong to G , and 2. the algorithm AddFinalEdgesOfObsoleteWalks() restores eto the graph. In other words, the extended obsolete edge is the first missing edge of an obsolete walk on the original feasible graph that is recovered by the algorithm. Sublemma 5. Let G be a feasible graph, i.e., a subgraph of the footmarks of computation walks with respect to Eo and V0 , where Eo contains the final edges of all feasible and obsolete walks, and let ef be the final edge of all feasible walks. If G contains more than one walk, then every obsolete or embedded walk W must contain at least one edge that is not shared with any other walk W′in G. Proof. Assume for contradiction that there exists an obsolete or embedded walk W such that every edge in Wis shared with at least one other walk in G. Since G contains more than one walk, there exists another walk W′ = W that is either feasible or obsolete. Consider two possible cases: Case 1: Wcontains no merging edge with any other walk. In this case, either W and W′ have no common vertices, or they were split and never merged again. In both situations, the final edge of W cannot be part of W′ . Hence, there exists at least one edge in W (e.g., its final edge) that is not shared with W′, contradicting our assumption. 35 Algorithm 6 Pruning An Edge given non-feasible walk Input:G: Feasible Graph, Ef:Final edge of the feasible walk, W: Obsolete or Embedded Walk Output: The graph G′ in which an edge of W removed and there exists at least one feasible or obsolete walk. 1: function PruneWalk(GU, G, V0, Ef, W, preserveObsolete) 2: Let Eo← ∅ 3: Set e′←FindFirstMergingEdgeOrFinalEdge(G, W) 4: if preserveObsolete then 5: AddFinalEdgesOfObsoleteWalks(G, Eo, Ef)▷Add the end of obsolete edge to final edges 6: end if 7: Let G′←ComputeFeasibleGraph(G−e′, V0, Ef∪Eo)▷Remove e′from feasible graph if exists 8: return G′[E(G)\Eo]▷Do not recover removed edge, this ensure polynomial time complexity 9: end function 10: function FindFirstMergingEdgeOrFinalEdge(G, W) 11: Let ebe the first edge of walk W 12: while eis not the final edge of walk Wdo 13: if eis merging edge then 14: return e 15: end if 16: e←nextW(e) 17: end while 18: return e▷It returns final edge of computation walk if no mergin edge found 19: end function 20: procedure AddFinalEdgesOfObsoleteWalks(GU:In, G :In/Out, Eo:Out, Ef:In) 21: for all edgee = (u, v)∈E(GU)do 22: if e∈ E(G)and u=tfor any edge (s, t)∈Efthen 23: if uis incident to any node in V(G)and and tier(v)>0and PredG(v)=∅then 24: Let G←G+e 25: Let Eo←Eo∪ {e} 26: end if 27: end if 28: end for 29: end procedure 36 eo e′ p e′ ep W′ W Figure 10: Non-floor Extended Edge of Obsolete Edge Case 2: Wcontains at least one merging edge. Let e be the first merging edge in W , and let e′ be the edge in another walk W′ that merges into e . The edge e′must belong to some walk other than W—either feasible, obsolete, or orphaned. If e′ belongs to a feasible or obsolete walk, then e cannot also be part of that walk, because computation walks are paths, and including both e′ and e would cause a vertex to appear more than once.Thus, e is not shared with W′, contradicting our assumption. If e′ is an orphaned edge, then by Lemma 16, there exist two walks, say W′ and W′′ , both feasible or obsolete, such that one of them leads to the orphaned edge e′ . If W′ and W′′ are merged before reaching e , this contradicts the fact that e is the first merging edge in W . Hence, at least one of W′ or W′′ does not contain e, again showing that eis not shared with all other walks. Therefore, in all cases, there exists at least one edge in W that is not shared with any other walk, completing the proof. Corollary 1 (Correctness of FindFirstMergingEdgeOrFinalEdge()).Let G be a computation graph that contains at least two walks, each of which is either feasible or obsolete with respect to Ef. Then, FindFirstMergingEdgeOrFinalEdge() returns the first merging edge e on a feasible or obsolete walk W such that e is not contained in every feasible or obsolete walk in G . If no such merging edge exists, it returns the final edge of W. Proof. By Sublemma 5, any feasible or obsolete walk W in G must contain at least one edge that is not shared with every other such walk. Let e be the earliest such edge on W (i.e., closest to the beginning of the walk). If this edge is a merging edge, FindFirstMergingEdgeOrFinalEdge() will detect and return it. If no merging edge satisfies the condition, then the only candidate is the final edge of W , which is also not shared with every other walk. Hence, the algorithm correctly identifies the earliest such edge not shared across all walks, completing the proof. Sublemma 6. Given a feasible graph G , if an extended obsolete edge is not a floor edge, then the obsolete walk cannot be a nested obsolete walk. Conversely, any obsolete walk whose extended edge is a floor edge is a nested obsolete walk in G. Proof. Let eo be the non-floor extended obsolete edge. First, suppose eo is an extended obsolete edge of nested obsolete walk W . Then there exists an obsolete walk W′ where W is a subwalk of W′ . Since eo is not the floor edge, there exists predecessor ep = PredW ( eo ), and there exists the splitting edge e′ with eo in W′ but not in W . Then there also exists predecessor e′ p = PredW′ ( e ). But if e′ p = ep , then e′ = eo , which is a contradiction to the fact that eo is an extended obsolete walk. If ep = e′ p , this also contradicts that W is a subwalk of W′ . Hence an obsolete walk with non-floor extended edge is not a nested obsolete walk. Second, for any obsolete walk W whose extended edge e is floor edge, there exists another floor edge e′ , splitting from e , which belongs to a feasible or obsolete walk W′ in the feasible graph G . Then W is a subwalk of W′ , which means W is a nested obsolete walk by the definition, completing the proof. Sublemma 7 (Correctness of AddFinalEdgesOfObsoleteWalks()).Let Gin be the original input feasible graph with respect to Ef , a set of final edges, and let Gout be the output graph (a modified version of Gin ) of AddFinalEdgesOfObsoleteWalk() with given input Gin and Ef . Let Eo be the set of output edges of AddFinalEdgesOfObsoleteWalk(). Then, except for nested obsolete walks, after executing 37 AddFinalEdgesOfObsoleteWalks(), every obsolete walk has at least one extended obsolete edge in Gout , and that edge belongs to Eo Proof. Suppose, for contradiction, that there exists an obsolete walk W′ that is not extended by AddFinalEdgesOfObsoleteWalks() where W′is a subwalk of W. Then, W′ is the maximal prefix of W such that all its edges belong to G , and let f be the final edge of W′. Let e= (u, v) = nextW(f)be the next edge in Wimmediately following f. By construction, u∈V ( G ). Moreover, since W is a computation walk, e must satisfy one of the following: •eis a floor edge (i.e., tier(v)=0), or •ehas a precedent edge (i.e., PrecG(v)=∅). But AddFinalEdgesOfObsoleteWalks() does not add any floor extended edge; thus all obsolete walks which are not nested obsolete walks have an extended edge by sublemma 6. Thus, e satisfies the condition of the if statement in AddFinalEdgesOfObsoleteWalks(), and should have been added to G′ and to Eo . This contradicts the assumption that Wwas not extended. Therefore, except for nested obsolete walks, in the resulting graph Gout , every obsolete walk that is extendable under these conditions is indeed extended, and its newly added edge belongs to Eo. Note. The algorithm guarantees that once an edge is removed as part of a pruning step, it is never recovered in any subsequent phase. This invariant is essential to ensure that the number of feasible graph updates is polynomially bounded and no obsolete information re-enters the computation. Lemma 17 (Correctness Pruning a Walk).Let G be a feasible graph and W an obsolete or embedded walk in Gwith respect to Ef. If PruneWalk() is executed, then the resulting graph G′satisfies the following: • At least one feasible or obsolete walk from G is preserved in G′ if preserveObsolete flag is true and there is at least two such walk exists. •G′ is a subgraph of G with at least one fewer edge than G , where the first merging edge on an embedded or obsolete walk is removed, if it exists. • Sub-obsolete walk is not preserved in G unless the obsolete walk containg the sub-obsolte walk preserved. Proof. By corollary 1, a removable edge e′ is selected on W , being the first merging edge—or the final edge if no merging edge exists—that does not belong to all feasible or obsolete walks in G . This guarantees that removing e′does not eliminate all such walks from the graph. If preserveObsolete flag is true, the by sublemma 7, all next edges of obsolete walks are extended and stored in Eo except for nested obsolete walks, ensuring that obsolete walks without e′ remain valid after ComputeFeasibleGraph() is invoked, as confirmed in Lemma 15, otherwise all the feasible walks not contiaing e′is preserved by Lemma 15. Then, by Lemma 12, the final output is a feasible subgraph of G−e′ , defined with respect to Eo∪Ef and VO , and all step-pendant edges are removed where Eo is the set of extended obsolete edge if preserveObsolete is ture, otherwise Eois empty. Therefore, PruneWalk() correctly computes a feasible graph G′ in which the first merging edge e′ is removed from an obsolete or embedded walk W , while preserving at least one feasible or obsolete walk. Since no additional edges are added, G′ has at least one fewer edge than G , and if preserveObsolete is true, then there is at least one preserved obsolete walk which is not a nested obsolete walk of another walks. Lemma 18 (Time Complexity of AddFinalEdgesOfObsoleteWalks()).Let the input feasible graph have width w , height h , and a total of wh2 edges. Assume that all relevant edge and node sets, including Eo , E ( G ), and the predecessor set PredG ( v ), are stored as ordered sets. Then the algorithm AddFinalEdgesOfObsoleteWalks() runs in time O(wh3). 38 Proof. The outer loop iterates over at most wh2 edges from E ( G ) \Ef , each of which may potentially be re-added. For each edge ( u, v ): - Collecting ( u, v )incident to any node in V ( G )takes at most O ( wh2 )time and there are at most O ( wh2 )edges to inspect. - Verifying whether PredG ( v )  = ∅ or tier ( v ) = 0 takes at most O ( h )time. - Adding an edge to the graph takes O ( h )time, as the adjacency list of each vertex has size at most O(h). - Other set operations require O(log h)time due to ordered set representation. Therefore, the total time complexity is O(wh2·h) = O(wh3). Lemma 19 (Time Complexity of Pruning Walk).Let G be a feasible graph with width w and height h , such that the total number of edges is O(wh2). Then, the time complexity of PruneWalk() is bounded by O(h6w2). Proof. The procedure PruneWalk() consists of the following steps: • Calling FindFirstMergingEdgeOrFinalEdge(): This function scans the given walk W and returns either the first merging edge or the final edge. Since the length of the walk is at most O(wh), this step takes O(wh)time. • Calling AddFinalEdgesOfObsoleteWalks(): As shown in lemma 18, this step has time complexity O(wh3). • Calling ComputeFeasibleGraph(): This recomputes the feasible subgraph from G−e′ , using the updated Eoand V0. By lemma 14, this step takes O(h6w2)time. Therefore, the total time complexity is: O(h6w2) + O(wh3) = O(h6w2). 6.2 Searching For Computing-Redundant or Computing-Disjoin Edge To prune unnecessary or redundant edges from a feasible graph G , we first aim to identify computation walks that do not contribute uniquely to any accepting configuration. This is achieved by locating either a computing-disjoint edge or a computing-redundant edge within obsolete or embedded walks. The following definitions and lemmas formalize this identification process. Definition 38. Given a feasible graph G and a set of final edges Ef , an edge e is called a computingredundant edge if e belongs to a feasible walk with respect to Ef , and there exists another feasible walk W′with respect to Efin the feasible graph of G−e(with respect to Ef). An edge e is called a computing-disjoint edge if it does not belong to any feasible edge set with respect to Ef ; in other words, removing e does not eliminate any feasible walks in the feasible graph of G−ewith respect to Ef. Definition 39. Let G(0) be a feasible graph. For each i⩾ 0, define G(i+1) to be the graph obtained by applying PruneWalk() to G(i) without preserving obsolete walks, using a maximal computation walk Wi in G(i) that is not feasible with respect to ef. Let m < |E(G)|be the minimal integer such that either E(G(m)) = |Wm|or E(G(m)) = ∅. Let R = Wm which is the attempted walk applied to maximal pruned graph remvoing all the feasible walk. We refer to: •G(i)as the i-th pruned graph, •Wi(for 0< i < m) as an attempted walk, •G(m)as the maximal pruned graph, •Ras a critical attempted walk. 39 The following algorithm algorithm 7 attempts to isolate an edge that can be safely pruned without eliminating all feasible walks. It first take a computation walk, if it finds a feasible walk then it returns immediately. Otherwise, it iteratively removes edges in the walks from the graph using PruneWalk(), detecting a critical attempted walk which removes all the feasible walk to ef . When a critical attempted walk detected, it re-computes the feasible graph preserving obsolete walks from the last feasible graph before all the feasible walk removed in the pruned graph via the critical attempted walk by extending all the obsolete walks except for a nested obsolete walks by adding one more edge. Then it finds an obsolete walk using the next attempted walk on the the re-pruned graph. After that, it invokes FindDisjointEdge() to locate an edge that is not shared with the critical walk(the graph R ), ensuring its redundancy or disjointness. Remark 3. Although TakeArbitraryWalk() is called in algorithm 7, the algorithm is deterministic. Any consistent rule for selecting the initial or subsequent edge (e.g., always taking the first available edge) will lead to the same outcome. Sublemma 8. Let R be the critical attempted walk which prunes all the feasible walks from the feasible graph G by applying PruneWalk() without preserving obsolete walks. Let W be a walk on the feasible graph G′ obtained by applying PruneWalk() to G while preserving obsolete walks. Let es be the first edge of walk W not in walk R and em be the first merging edge if one exists, otherwise the last edge of W . Let W′ be the subwalk of W from es to em . Then an edge e in W′ is a computing-disjoint edge unless it is a computing-redundant edge. em er ed feasible walk R W (a) Case where edis behind er em er e′ m ed merging edge R W (b) Case where edis ahead of er Figure 11: A feasible edge on obsolete walk after all feasible walks removed Proof. Suppose W′ contains a feasible edge. Let er be a feasible edge on R , and let ed be the feasible edge on W′ . Let Wf be a feasible walk. By the assumption, it is not a computing-redundant edge; thus Wfshould contain both emand ed. Then we have two cases. 1) Case where eris ahead of emin Wf. In this case, er is behind em ( er cannot be em ; otherwise, Wf cannot contain any edge of W′ ). Then, when em is removed, the feasible walk should be preserved by lemma 15 since it contains both er and ed and does not contain the removed edge em . This is a contradiction to the fact that R is the critical attempted walk pruning the remaining feasible walks. 2) Case where eris ahead of em. In this case, there exists a merging edge between Wf and R before em , which also contradicts that em is the first merging edge. In both cases, we have contradictions, thus, edis a computing-disjoint edge by definition. 40 Algorithm 7 Find Computing-Redundant or Computing-Disjoint Edge for Pruning Input:GU : Original Feasible graph, V0 : Inital edges of computation walks, ef : the final edge of feasible graph and feasible walks. Output: Computing-Reundant or Computing Disjoint Edge of feasible graph GU with respect to Ef={ef}, V0. 1: function FindFeasibleOrDisjointEdge(GU, V0, ef)▷ V0 :initial node of walks, ef : the end of feasible walks 2: Let G←GU 3: Let Ef← {ef}▷Ef: set of ends of feasible or obsolete walks 4: Let R←an empty graph 5: while Gis not empty do loop until only one walk remains on the graph or a feasible walk is found] 6: Let W←TakeArbitraryWalk(G, V0) 7: Let e←the last edge of W▷Wis either a feasible or an obsolete walk 8: if e=efthen ▷ e is not obsolete walk but feasible walk 9: return e 10: else if Ris not empty then ▷Feasible edge removed once 11: return FindDisjointEdge(R, W)▷Return disjoint or redundant edge 12: else if Gis not empty then ▷ W can be embedded walk not obsolete walk 13: Set H←PruneWalk(GU, G, V0, Ef, W, False) 14: if His empty then ▷ H does not cotaine any of Ef 15: Add all edges and vertices of Wto R 16: Set G←PruneWalk(GU, G, V0, Ef, W, True) 17: else 18: Set G←H 19: end if 20: end if 21: end while 22: return NIL 23: end function 24: function TakeArbitraryWalk(G, V0)▷Take Arbitrary Walk from Start Nodes ▷Any consistent choice (e.g., always first edge) works; result is deterministic 25: Let Sbe the empty dynamic array of Transition cases ▷Empty Surface 26: Let Wbe the empty list of edges 27: Let ebe an edge in Gincident with any node in V0if exists, otherwise NIL ▷We can choose the first such edge 28: while e=NIL do 29: Update surface S[index(u)] with the transition case to which node ubelongs 30: Append eto walk W 31: Set e←an edge of NextG(e)on surface Sif exists, otherwise NIL▷S[i] = PrecG(v′)where (u′, v′)is a next edge 32: end while 33: return W 34: end function 35: function FindDisjointEdge(R, W)▷ Check indirect precedents, To make orphaned walks, ceiling edges of another walk need 36: Let ebe the first edge of walk W 37: while eis not NIL do 38: if e∈ E(R)then 39: return e 40: end if 41: e←nextW(e)▷If nextW(e)does not exist then e is NIL 42: end while 43: return NIL 44: end function 41 •Otherwise, the verified feasible edges in Evare removed from Q, and the algorithm proceeds. Hence, the invariant continues to hold: H grows only via feasible edges, Q shrinks by removing only verified entries, and accepting paths are immediately detected. Termination: In each iteration, at least one edge is removed from Q and never re-added. Since Q contains only boundary edges, and the number of edges in G is finite, the total number of iterations is bounded by |E(G)|. Therefore, the loop terminates in finite time. Conclusion: Upon termination, H contains all vertices and edges reachable from V0 (via e ) by feasible computation walks in G . The function returns True if and only if there exists suc such walk reaches an accepting state. Lemma 26 (Time Complexity of Checking Existence of Accepting State of All Computation Walks). Let G be a dynamic complete computation graph with width w and height h . The total number of edges in Gis at most O(wh2). Let Tvdenote the time complexity of the VerifyExistenceOfWalk() procedure. Then, the total time complexity of the algorithm IsAcceptedOnFootmarks() in algorithm 9 is bounded by O|E(G)| · Tv=O(wh2·Tv). Proof. The number of edges in G is at most O ( wh2 ). Since there are at most wh nodes, and each node has at most hincident edges, the CollectBoundaryEdges() procedure takes O(wh2)time per call. In IsAcceptedOnFootmarks(), the ExtendByVerifiableEdges() procedure calls VerifyExistenceOfWalk() for edges in the boundary set Q. Each edge is processed at most once: it is added to Ev and removed from Q exactly once. Therefore, the number of calls to VerifyExistenceOfWalk() is O(|E(G)|) = O(wh2). Since each call to VerifyExistenceOfWalk() costs Tvtime, the overall time complexity is O(wh2·Tv). In this section, we presented algorithms that, starting from already visited nodes, explore boundary edges to expand and verify all feasible computation paths within polynomial time. We proved their correctness and analyzed their time complexity by leveraging the verification algorithm for computation walks to specific edges. 7.2 Polynomial Algorithm for any NP Problem(Simulation of Verifier for All Certificates) In this subsection, we provide a deterministic, polynomial-time algorithm that simulates the verifier over a filtered computation graph. This simulation replaces the nondeterministic certificate-guessing process with a structured traversal of feasible computation paths. Thus, this algorithm effectively constitutes a polynomial-time reduction from any NP decision problem to a deterministic decision procedure, thereby supporting the claim that P=NP. This algorithm decides, within polynomial time bounds, whether a given verifier Turing Machine (TM) accepts the input problem instance for any certificate string. The structures used during simulation, denoted by G and H , represent a compressed computation graph in the form of a directed graph. Here, G is the dynamically constructed computation graph, while H maintains the set of visited edges to avoid redundant computations. This approach minimizes repeated traversals of identical paths, thereby improving search efficiency. Unlike the exponential-time version that constructs the entire simulation tree, this method expands the computation graph on-demand by exploring only necessary paths, thereby managing the search space and computational load efficiently within polynomial time. Before we prove the correctness of the final algorithm SimulateVerifierForAllCertificates(), we recall the fundamental idea that a valid computation walk corresponds to a valid sequence of instructions executed by a nondeterministic Turing machine. In the previous subsection, we have shown how to verify the existence of such a computation walk in a given computation graph. That is, given a computation graph, we determine whether there exists a walk from the initial node to an accepting configuration that respects the transition rules of the machine. 48 However, our goal is to simulate the verifier for all certificates. This means we are no longer verifying the existence of a walk in a fixed graph, but rather checking whether, for a given input x to an NP verifier V , there exists some certificate y such that the combined input ( x, y )leads to an accepting computation path. To achieve this, we must ensure two properties: • Soundness: If a computation walk exists in the dynamically constructed computation graph, then there exists an accepting instruction sequence for some certificate. • Completeness: The dynamic computation graph must include all edges that could possibly lead to an accepting path under some certificate. That is, it must simulate every possible transition of the verifier Vover all possible certificate strings. The algorithm SimulateVerifierForAllCertificates() is based on iteratively applying IsAcceptedOnFootmarks(), which expands the graph starting from initial nodes and edges. As we already proved the correctness of IsAcceptedOnFootmarks(), we now leverage that result to verify the correctness of the entire simulation procedure. The entire exploration process relies on a simple yet powerful observation: once a single reachable edge is provided, the computation graph does not need to be fully simulated from scratch. Instead, it is sufficient to initialize the computation graph with only one edge that belongs to some feasible computation path. This contrasts with the exponential-time simulation presented in Section 4.4, which explores all possible certificates through exhaustive enumeration. In contrast, the current approach achieves polynomial-time simulation via boundary-guided expansion from a single reachable edge. Algorithm 10 Simulate Verifier For All Certificates Input:L: problem instance string ending with delimiter #,m: certificate length, 1: q0: initial state of verifier TM, Σ: input alphabet, δ: transition function, 2: Q: Set of state of machine including, F={qacc, qrej}: set of final states Output: The decision result: Yes if any certificate makes verifier accept, otherwise No 3: function SimulateVerifierForAllCertificates(L, m, q0,Σ, δ, Q) 4: Let Gbe a NPDynamicComputationGraph 5: Let G.Initialize(L, m, q0,Σ∪ {ϵ}, δ, Q) 6: Let s←L[0] ▷Problem Instance is not empty string 7: Let v0be the unique node in Vq0,s 0,0▷v0: vertex at index 0, tier 0, state q0, symbol s 8: Let E0←G.GetNextEdges(v0)▷NextG(v0) 9: Let V0← {v0} 10: Let H←G(V0, E0)▷Computation Graph 11: if IsAcceptedOnFootmarks(G, H, V0)then ▷ v0:Initial vertex where state(v0) = q0 12: return Yes 13: end if 14: return No 15: end function Sublemma 9. The method GetFloorNextEdges() returns nodes only for the tape symbol of L or the possible certificate strings within the non-empty tape area, given the problem instance string L and certificate length m. Proof. The method GetFloorNextEdges() returns a floor edge ( u, v )where v is a computation node with cell index i′at which the next read/write occurs. It distinguishes the following cases: • If i′<len ( L )(input region), the algorithm deterministically returns the unique edge leading to a node labeled with s′=L[i′], the corresponding input symbol. • If i′∈ [ len ( L ) ,len ( L ) + m )(certificate region), the algorithm nondeterministically includes all possible edges to nodes labeled with each s′∈Γ, thus accounting for all possible certificates. 49 Algorithm 11 NP Dynamic Compuation Graph Description: This Graph is a Dynamic Graph for NP verifier input string and all certificates 1: class NPDynamicComputationGraph 2: field q0: a turing machine states represnting the initial state 3: field L: an empty string representing taple alphabet 4: field m: Integer representing length of certificate 5: field Γ: Set of all symbols of the Turing machine 6: field δ: Transition of Turing mahine 7: V: Dynamic Array representing computation node 8: function Initialize(L′, m′, q′ 0, Q, , Σ′, δ′, F ′) 9: Set (q0, L, m, Q, F, δ)←(q′ 0, L′, m′, Q′, F′, δ) 10: Set Γ←Σ∪ {ϵ} 11: end function 12: function GetNextEdges(v, h)▷ NextG(v)with tier of its head at most h 13: Let E←GetFloorNextEldges(v) 14: Let E′←GetNonFloorNextEldges(v, h) 15: return E∪E′ 16: end function 17: function GetNonFloorNextEdges(v, h) 18: Let (i′, q′)←(next_index(v),next_state(v)) 19: for all (s′, q′, t′)such that s′∈Γand q′∈Qand 1< t′⩽hdo 20: for all v∈Vq′,s′ i′,0do 21: Add (v, v′)to E 22: end for 23: end for 24: end function 25: function GetFloorNextEdges(v) 26: Let Ebe an empty set of compuation edge 27: Let (i′, q′)←(next_index(v),next_state(v)) 28: if L[i′]is defined then 29: Let v′←the unique node u∈Vq′,s′ i′,0with s′=L[i′] 30: Add (v, v′)to E 31: else if i′<0or i′>len(L) + mthen 32: Let v′←the unique node in Vq′,s′ i′,0with s′=ϵ 33: Add (v, v′)to E 34: else 35: for all s′∈Γdo 36: Let v′←the unique node in Vq′,s′ i′,0 37: Add (v, v′)to E 38: end for 39: end if 40: end function 41: 50 • If i′< 0or i′⩾len ( L )+ m (out-of-bounds access), the algorithm includes only the edge corresponding to the blank symbol ϵ. In all cases, we only have the symbol at tape index i′ in the input string L , or in all possible certificate strings, or the blank symbol for the empty tape area. Lemma 27 (Soundness of Simulating Verifier For All Certificates).Let M be an NP verifier and L be an input string for promblem instance. SimulateVerifierForAllCertificates() algorithm 10 returns Yes if and only if there exists a certificate yof length msuch that M(Ly) = accept. Proof. First, we prove that if SimulateVerifierForAllCertificates() returns accept , there exists a compuation walk reaching the accepting state qacc ∈F by lemma 25 and all its floor edges are provided by GetFloorNextEdges(), which guarntees that there exists a certificate y of length m . Thus, we have that M ( Ly ) = accept since the computation walk is the simulation of Turing machine transitions for the tape string. Now, we prove that if there exists a computation walk W for some certificate y such that the verifier M on input ( L, y )reaches an accepting configuration, then SimulateVerifierForAllCertificates() constructs a corresponding path in its dynamically constructed computation graph and returns Yes. Assume, for contradiction, that SimulateVerifierForAllCertificates() includes a computation walk in the graph H (constructed via IsAcceptedOnFootmarks()) that is not realizable by any valid certificate y of length mfor input L. Let W = ( e0, e1, . . . , ek )be a partial valid computation walk, but suppose W′ = ( e0, e1, . . . , ek, ek+1 ) contains an edge ek+1 that is not valid under any such certificate. Since IsAcceptedOnFootmarks() only explores edges returned by GetNextEdges(), and that procedure generates only edges consistent with the verifier’s transition rules, this leads to a contradiction. Now note that, except for the floor edges of W , all other edges are uniquely determined by the surface structure of the computation walk. Without loss of generality, assume that ek+1 is a floor edge (i.e., of tier 0). By sublemma 9, the returned edge ( v, v′ )by GetFloorNextEdges() is consistent with a feasible configuration of the verifier on some input ( L, y ), meaning no invalid edge can be introduced into H . This contradicts the assumption that Hcontains a computation walk not realizable by any valid certificate. Finally, since the algorithm returns Yes only when it reaches a node labeled with qacc ∈F , and such a node is reachable only via a valid computation walk corresponding to some certificate y , the result is sound. Lemma 28 (Completeness of Simulating Verifier For All Certificates).We now prove the completeness of the algorithm SimulateVerifierForAllCertificates(). That is, we must show that: For every possible accepting computation walk corresponding to some certificate y for input L , the algorithm can generate all the required edges and thus simulate the accepting path without being blocked. Proof. We proceed by contradiction. Suppose there exists a valid accepting computation walk W (for some y such that V ( L, y )accepts) which cannot be fully simulated by our algorithm. Then there exists a node v on W and a valid successor node v′ in W such that the edge e = ( v, v′ )is missing from the computation graph G constructed by the algorithm. Now, consider how the algorithm GetNextEdges() generates possible successors from node v . The function distinguishes between floor edges and non-floor edges. Case 1: eis a floor edge This corresponds to a transition based on the original input string L (since floor edges reflect fixed transitions on the input tape). In this case, GetNextEdges() internally calls GetFloorNextEdges(), which examines the current tape position and verifies whether the symbol under the head matches the transition in the verifier’s instruction set. • If i′<len ( L )(input region), the algorithm deterministically returns the unique edge leading to the node labeled with s′=L[i′], the corresponding input symbol. • If i′∈ [ len ( L ) ,len ( L ) + m )(certificate region), the algorithm nondeterministically includes all possible edges to nodes labeled with each s′∈Γ, thus accounting for all possible certificates. 51 • If i′< 0or i′⩾len ( L ) + m (out-of-bounds), the algorithm includes only the edge corresponding to the blank symbol ϵ. In all cases, GetNextEdges() includes all possible valid edges from v. Case 2: eis a non-floor edge Here, e corresponds to a transition involving the certificate tape or work tape. GetNextEdges() calls GetNonFloorNextEdges(), which considers the current surface configuration and returns all possible valid next edges consistent with the verifier’s transition function. Importantly: • The tier of a successor node is always determined based on the surface of the current computation walk. • When expanding edge e , although the surface transition case may have a tier t′ greater than the current maximum tier tm, the successor node’s tier is at most tm+ 1. •Nodes with tiers higher than tm+ 1 are invalid during the expansion of e. • The function returns edges ( v, v′ )for all possible symbols and states with tiers up to tm +1, ensuring no valid nodes are omitted during expansion. Therefore, if e = ( v, v′ )is a valid non-floor transition in the computation walk, it must be among the edges returned by GetNonFloorNextEdges(). Consequently, the algorithm creates and includes such an edge in G, contradicting the assumption that ewas missing. Final note: Except for floor edges, all other edges are determined by the surface of the computation walk. Thus, the only potential risk of missing edges could be from floor edges. However, as shown, GetFloorNextEdges() exhaustively covers all possibilities based on the fixed input string L. Hence, every valid computation walk for any certificate is correctly simulated, and all edges necessary for that simulation exist in the constructed graph G. Therefore, the assumption leads to a contradiction in all cases, proving that the algorithm is complete. Lemma 29 (Time Complexity of Simulating Verifier For All Certificates).The time complexity of the algorithm SimulateVerifierForAllCertificates() is asymptotically the same as that of IsAcceptedOnFootmarks(), which it invokes internally. More precisely, if G is the np computation graph with width w and height h , then the total time complexity of SimulateVerifierForAllCertificates() is bounded by O|E(G)| · Tv=O(wh2·h10w4) = O(h12w5), where |E ( G ) | = O ( wh2 )is the total number of edges in G , and Tv = O ( h10w4 )is the time complexity of the VerifyExistenceOfWalk() procedure (by lemma 23). Proof. The dominant computation in SimulateVerifierForAllCertificates() is the call to IsAcceptedOnFootmarks(), which systematically explores and verifies edges in the computation graph G. By Lemma lemma 26, IsAcceptedOnFootmarks() performs at most O ( wh2 )calls to VerifyExistenceOfWalk(), each costing O(h10w4)time by lemma 23. All other steps in SimulateVerifierForAllCertificates(), such as graph initialization and edge generation, are polynomial in wand h, and do not exceed the cost of the main subroutine. Thus, the total time complexity is O(wh2·h10w4) = O(h12w5). 52 7.3 Reduction from NP to P via Feasible Graph Simulation Given any problem in NP, let M be its polynomial-time verifier. We construct a computation graph G representing all possible transitions of M over problem instance input L and all possible certificates length of m . We then extract the feasible subgraph Gfeasible using a polynomial-time filtering process defined in section 5. Finally, the algorithm SimulateVerifierForAllCertificates() explores computation walks within Gfeasible to determine whether an accepting path exists. This entire process replaces the nondeterministic existential certificate search with a deterministic graph traversal, completing the reduction. Theorem 30. The algorithm SimulateVerifierForAllCertificates() solves all NP problems in polynomial time. Therefore, P=NP. Proof. We will prove that the algorithm SimulateVerifierForAllCertificates() solves all NP problems in polynomial time by leveraging the previous lemmas regarding the correctness and time complexity of the algorithm. 1. Correctness and Certificate Coverage: The algorithm SimulateVerifierForAllCertificates() correctly simulates the verifier for all certificates of the acceptor Turing Machine. It iterates over all inputs s∈ Γfor the certificate tape area and constructs a footmarks of all possible computation walks starting from the initial configuration corresponding to L [0] by lemma 27. For each certificate, it simulates the Turing machine’s transitions. If the Turing machine reaches an accepting state, the certificate is deemed valid and the algorithm returns "yes"; otherwise, it rejects the certificate by returning "no." Thus, the algorithm verifies the validity of every certificate by simulating the Turing machine’s verifier for all possible inputs. By lemmas 27 and 28, this simulation correctly identifies all and only the valid certificates for which there exists an accepting computation walk. Therefore, the algorithm is correct for all inputs. 2. Polynomial Time Complexity: From lemma 29, the time complexity of the algorithm SimulateVerifierForAllCertificates() is polynomial in the input size n . More precisely, by lemma 29, the runtime is bounded by: h12w5 where: •n is the input size n where n = m + |L| is the total input size, m is the certificate length, and L is the problem instance string for the verifier. •p ( n )is a polynomial bounding both width and height of graph (see lemma 6) where p ( n ) = C·nc for some constant Cwhere c= 17 is the total exponent derived from h12w5. Hence, the total running time is polynomial in p ( n ) c , hence polynomial in the input size n . Moreover, there exisits polynomial function p′′ ( |s| ) = |t| by definition 6, thus we have p′ ( n′ ) = C′·nc′ where n′ = |L| , original NP problem input size,p′(n′) = p(p′′(n′)). Although our simulation uses dynamic arrays that allow amortized constant-time access, the twodimensional structure of the computation graph introduces additional overhead, which is not accounted for in the prior time complexity analysis. As a result, the total simulation time is bounded by T′ ( n ) = O ( T ( n ) ·p ( n ) ′2 ), which reflects the worst-case number of accesses and resizing operations. Here, T ( n ) denotes the time complexity of the underlying algorithm without considering data structure overhead. Furthermore, although the algorithm is described using high-level models such as the RAM model or graph traversal frameworks, it can be simulated on a deterministic single-tape Turing machine with polynomial overhead. By Cook’s theorem [ 4 ], any RAM algorithm running in T′ ( n )time can be simulated by a Turing machine in time O ( T′ ( n ) 3 ). Thus, by lemma 1, we obtain a polynomial-time algorithm for all NP probelms . Therefore, the entire NP problem remains within the class Punder standard complexity-theoretic definitions. 3. Solving NP Problems: Since SimulateVerifierForAllCertificates() decides any language in NP in deterministic polynomial time, it follows by definition that P=NP. 4. Conclusion: The algorithm solves every problem in NP within polynomial time. Therefore, we conclude that P=NP . 53 8 Implications and Discussions The direct proof that P = NP provided in this paper has far-reaching implications for both theoretical and practical aspects of computer science. First and foremost, it fundamentally alters our understanding of computational complexity, as it shows that every problem whose solution can be verified in polynomial time can also be solved in polynomial time. This breakthrough resolves the long-standing question of P vs. NP and opens up new avenues for algorithmic design and optimization. The immediate practical impact of this result is immense, especially in fields such as cryptography, where many systems rely on the assumption that P = NP . The implications for encryption algorithms and secure communication protocols are profound, as they may no longer be as secure as previously thought. As a result, further research into cryptographic methods will be necessary to adapt to this new understanding of complexity. Additionally, this result may change the landscape of artificial intelligence and machine learning, where NP-complete problems often arise in optimization tasks. With the ability to solve these problems in polynomial time, we may see significant advancements in algorithmic efficiency, enabling more powerful and scalable AI systems. One of the key consequences of this proof is its effect on the landscape of time complexity classes. In computational theory, problems are classified into different complexity classes based on how much time (or resources) they require to solve. Before this result, the major open question was whether the class of problems that can be solved in polynomial time, denoted as P , is the same as the class of problems whose solutions can be verified in polynomial time, denoted as NP. Now that we have established that P=NP, the implications for complexity theory are significant: • NP-complete problems, which were previously considered to be some of the hardest problems in NP, can now be solved in polynomial time, thereby collapsing the class of NP problems into the class P. • The class co-NP, consisting of problems whose complements are in NP, also collapses to P, as we now have P=NP =co-NP. This breakthrough also suggests that EXPTIME, the class of problems solvable in exponential time, remains a distinct class from P. Specifically, while P = NP = co-NP , it is still true that P<EXPTIME , meaning that problems solvable in exponential time cannot be reduced to polynomial time. The relationships between P , NP , co-NP , and EXPTIME may prompt the need for a deeper understanding of the fine structure within these classes. However, despite this groundbreaking theoretical result, practical applications are not immediate. The proof relies on a novel computation model and the simulation of Turing machines, which in turn depends on the concept of a Feasible Graph to ensure polynomial-time simulations. While this approach provides a clear theoretical path to solving NP problems, current computing technology, based on traditional Turing machines, is not yet capable of performing such simulations efficiently. As a result, the direct construction of practical solutions for NP-complete problems is not feasible with current computational resources. Thus, although the theoretical proof that P = NP is a major step forward, additional research will be necessary to develop algorithms that can efficiently solve NP problems in practice. This will likely involve exploring new computational paradigms, hardware improvements, and optimizations that can handle the complexity of polynomial-time simulations in realistic settings. Furthermore, there may be additional challenges related to the scalability of such solutions, especially for large problem instances, which will require further investigation and refinement. This result opens new directions for exploring the relationships between these complexity classes. Research into the separations between other complexity classes such as BPP,IP, and PSPACE, and understanding their relationship with P and NP , will become an important focus of future work. Furthermore, reevaluating existing models and approaches in computational science could lead to new paradigms in both theoretical and practical aspects of computational theory. 54 9 Conclusion In this paper, we presented a groundbreaking solution to the P = NP problem by introducing a new computation model that enables the deterministic simulation of NP algorithms. Our model shifts the focus from attempting to simulate nondeterministic Turing machines directly to simulating certifiers efficiently, providing a novel perspective on the relationship between NP and deterministic computation. Through the introduction of feasible graphs, we show that the simulation of NP problems can be performed in polynomial time, establishing that P=NP. This process can be viewed as an explicit polynomial-time reduction from any NP problem to a deterministic decision procedure: given a verifier M for an NP language, we construct a computation graph, extract its feasible subgraph, and deterministically simulate all valid computation walks within polynomial time. In contrast to guessing a correct certificate, the feasible graph method deterministically filters and verifies all potentially accepting paths, yielding a concrete reduction from existential verification to constructive decision. This result has profound implications for theoretical computer science and various fields that rely on computational complexity. By demonstrating that NP problems can be solved in polynomial time, we effectively prove that P = NP, resolving one of the most important open questions in the field. Our approach not only contributes to the understanding of NP problems but also paves the way for future research in polynomial-time algorithms and complexity class separations. This reduction-based approach also opens the door to generalized algorithmic frameworks for simulating nondeterministic computations deterministically, and may inspire new techniques for analyzing complexity classes beyond NP. Future work will focus on exploring the broader implications of this result, including its impact on cryptography, optimization, and artificial intelligence. Additionally, refining our model to handle a wider range of NP-complete problems could further enhance the practical applicability of this solution in real-world scenarios. 55 References [1] 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. [2] T. Baker, J. Gill, and R. Solovay. Relativizing proofs of the p = np problem. SIAM Journal on Computing, 4(4):297–309, 1975. [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. [4] Stephen A Cook and Robert A Reckhow. Time-bounded random access machines. In Proceedings of the fourth annual ACM symposium on Theory of computing, pages 73–80, 1972. [5] Reinhard Diestel. Graduate texts in mathematics: Graph theory. Heidelb: SpringerVerlag, third edition edition, 2005. [6] James L Hein. Theory of computation: an introduction. Jones and Bartlett Publishers, Inc., 1996. [7] John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60–65, 2001. [8] Richard M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85–103, 1972. [9] Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson, Upper Saddle River, NJ, June 2005. [10] A. Razborov and S. Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24–35, 1993. [11] Ping Zhang and Gary Chartrand. Introduction to graph theory. Tata McGraw-Hill, pages 2–10, 2005. 56 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 graph representing a Turing machine execution path. Also referred to as a computation path due to injectivity. section 4 Transition Case A set of computation nodes sharing the same cell index, current state, symbol, and tier. section 4 Precedent Node A transition case matching the last state and symbol of a computation node (tier difference is +1). section 4 Previous/Nex Edge (Walk-based ) For edge ei in a computation walk, the previous is ei−1 and the next is ei+1. section 4 Previous/Next Edges (Graph-based) For edge e = ( u, v )in a computation graph, all incoming/outgoing edge from vertex v. section 4 Succedent Nodes Set of nodes v′for which a given node vis the precedent. section 4 Surface The sequence of latest transition cases for each cell position, as visited by a computation walk. section 4 Tier A hierarchical level of computation nodes and transition cases indicating the number of visiting of the cell. section 4 57 Algorithm 18 GetCeilingAdjacentEdges Description: Returns the set of edges ceiling adjacent to e0toward Efin computation graph G. 1: function GetCeilingAdjacentEdges(G, e0, Ef) 2: Let C← ∅ ▷Collected ceiling-adjacent edges 3: Let i←index(init(e0)) 4: Let Ev← {(i, e0)}▷Visited edge set 5: Let Qbe a queue initialized with (i, e0) 6: if e0∈Efthen 7: Enqueue (i′, e0)to Qwhere i′= index(term(e0)) 8: end if 9: while Qis not empty do 10: Dequeue (i, e)from Q 11: Add (i, e)to Ev 12: Let ube the incident node of ewith index(u) = i 13: if uis a folding node or u= term(e0)then 14: Let P←PrecG(e) 15: for all e′∈Psuch that (i, e′)/∈Evdo 16: Enqueue (i, e′)to Q 17: end for 18: else 19: Add all incoming edges of uto C 20: end if 21: end while 22: return C 23: end function Algorithm 19 Check Index Adjacency Description: Returns true if edge f is index-adjacent to Es , final edge set Ef , and initial vertex set V0 . 1: function IsIndexAdjacent(G, f, Es, Ef, V0) 2: Let idx ←the index of edge slice Es ▷All edges in Es share the same edge index 3: Let (u, v)←f 4: if edge list of uin Es is not empty or edge list of vin Es is not empty then 5: return True 6: end if 7: if ( G.IsFoldingNode ( u )and index ( u ) = idx )or (G.IsFoldingNode(v)and index(v) = idx)then ▷ Condition 2: Folding node with common index 8: return True 9: end if 10: if (u, v)∈Efand index(v) = idx then ▷Final vertex with common index 11: return True 12: end if 13: if u∈V0and index(u) = idx then ▷Final vertex with common index 14: return True 15: end if 16: return False 17: end function 64