[proofplan] We construct a deterministic decider for $\mathrm{PATH}$ using breadth-first search from the start vertex $s$. The algorithm maintains the set of discovered vertices and a queue of discovered vertices whose outgoing edges have not yet been scanned. We prove that a vertex is discovered exactly when it is reachable from $s$ through edges already explored, and then bound the running time by observing that each vertex is enqueued at most once and each directed edge is scanned at most once. [/proofplan] [step:Define the breadth-first search decider for $\mathrm{PATH}$] Let $M$ be the following deterministic Turing machine. On input $w$, the machine first checks whether $w$ is a valid standard binary adjacency-list encoding of a triple $\langle G,s,t\rangle$, where $G=(V,E)$ is a finite directed graph and $s,t\in V$. If the encoding is invalid, $M$ rejects. Assume now that $w=\langle G,s,t\rangle$ is valid. Let $D\subseteq V$ denote the set of discovered vertices, and let $Q$ denote a first-in-first-out queue whose elements are vertices of $G$. The machine initializes $D:=\{s\}$ and initializes $Q$ with the single element $s$. While $Q$ is nonempty, $M$ removes the front vertex $u$ from $Q$ and scans every directed edge $(u,v)\in E$ appearing in the adjacency list of $u$. If $v\notin D$, then $M$ inserts $v$ into $D$ and appends $v$ to the back of $Q$. If this insertion gives $v=t$, then $M$ accepts. If the loop terminates without discovering $t$, then $M$ rejects. In the case $s=t$, the initialization already discovers $t$, so $M$ accepts immediately. [/step] [step:Prove that every discovered vertex is reachable from $s$] We prove by induction over the order in which vertices are inserted into $D$ that every vertex in $D$ is reachable from $s$ by a directed path in $G$. The first inserted vertex is $s$, and $s$ is reachable from itself by the path of length $0$. For the induction step, let $v\in V$ be inserted into $D$ while scanning an edge $(u,v)\in E$ from a vertex $u$ already in $D$. By the induction hypothesis, there exist an integer $m\geq 0$ and vertices $v_0,\dots,v_m\in V$ such that $v_0=s$, $v_m=u$, and $(v_{i-1},v_i)\in E$ for every $i\in\{1,\dots,m\}$. Appending the edge $(u,v)$ gives the directed path $v_0,\dots,v_m,v$ from $s$ to $v$. Therefore every discovered vertex is reachable from $s$. [guided] We need to justify that the algorithm never accepts for the wrong reason. The only way the machine accepts is by discovering $t$, so we prove the stronger invariant that every discovered vertex is reachable from $s$. The invariant is proved by induction on the insertion order into $D$. At initialization, the only discovered vertex is $s$. This vertex is reachable from $s$ by the directed path of length $0$, namely the one-term sequence with vertex $s$. Now suppose the invariant holds before some new vertex $v$ is inserted. By the definition of the algorithm, $v$ is inserted only while scanning an outgoing edge $(u,v)\in E$ from a vertex $u$ that was already discovered. Since $u\in D$, the induction hypothesis gives a directed path from $s$ to $u$. Write this path as vertices $v_0,\dots,v_m\in V$, where $v_0=s$, $v_m=u$, and each consecutive pair satisfies $(v_{i-1},v_i)\in E$. Because the scanned edge $(u,v)$ also lies in $E$, the extended sequence $v_0,\dots,v_m,v$ is a directed path from $s$ to $v$. Thus the newly discovered vertex is reachable, and the invariant is preserved. Consequently, if the machine accepts because it discovered $t$, then $t$ is reachable from $s$ in $G$. [/guided] [/step] [step:Prove that every reachable vertex is eventually discovered] Let $r\in V$ be reachable from $s$. Choose a directed path $v_0,\dots,v_m$ from $s$ to $r$ with $v_0=s$ and $v_m=r$. We prove by induction on $i\in\{0,\dots,m\}$ that $v_i$ is eventually inserted into $D$. For $i=0$, the vertex $v_0=s$ is inserted during initialization. Suppose $v_i$ is eventually inserted into $D$ for some $i<m$. When $v_i$ is inserted, it is appended to $Q$. Since vertices are never removed from $Q$ except by being scanned, the loop eventually removes $v_i$ from $Q$ and scans every edge in the adjacency list of $v_i$. In particular, it scans $(v_i,v_{i+1})\in E$. If $v_{i+1}$ is already in $D$, then it has already been discovered; otherwise the algorithm inserts $v_{i+1}$ at that scan. Hence $v_{i+1}$ is eventually inserted into $D$. By induction, $r=v_m$ is eventually discovered. [/step] [step:Conclude that the decider accepts exactly the strings in $\mathrm{PATH}$] If $M$ accepts a valid input $\langle G,s,t\rangle$, then $t$ was discovered, so the previous soundness argument shows that $t$ is reachable from $s$. Hence $\langle G,s,t\rangle\in \mathrm{PATH}$. Conversely, if $\langle G,s,t\rangle\in \mathrm{PATH}$, then $t$ is reachable from $s$. The completeness argument shows that $t$ is eventually inserted into $D$, and the machine accepts when this happens. Therefore $M$ decides $\mathrm{PATH}$. [/step] [step:Bound the running time by a polynomial in the input length] Let $n=|V|$ be the number of vertices and let $m=|E|$ be the number of directed edges in $G$. Each vertex is inserted into $D$ at most once, because insertion is performed only after testing that the vertex is not already in $D$. Hence each vertex is appended to $Q$ at most once and removed from $Q$ at most once. When a vertex $u$ is removed from $Q$, the algorithm scans exactly the adjacency list of $u$, so over the full run each directed edge in $E$ is scanned at most once. With standard data structures for the discovered set and queue, the total running time is $O(n+m)$ after parsing the input. In a standard adjacency-list encoding, the input length is at least proportional to $n+m$, up to the fixed binary overhead needed to name vertices and delimit lists. Thus the running time is bounded by a polynomial in the input length. Since $M$ is a deterministic decider for $\mathrm{PATH}$ with polynomial running time, $\mathrm{PATH}\in \mathrm{P}$. [/step]