Need help to proof that NP⊆NP4


Take any language $L in mathsf{NP}$ and let $T$ be a non-deterministic polynomial-time Turing machine that decides $L$. Let $Gamma$ and $q_A$ be the tape alphabet and the accepting state of $T$, respecitvely.

Create a new Turing machine $T’$ that has the same states of $T$ plus four additional states $q_1, q_2, q_3, q_4$.
$T’$ is obtained from $T$ by:

  • Replacing each transition $(q, a) to (q_A, b, m)$ of $T$ (where $q$ is a state of $T$, $a,b in Gamma$, and $m in {text{left}, text{right}, text{stay}}$ is the movement of the head) with the four transitions $(q, a) to (q_i, b, m)$ for $i in {1,2,3,4}$.

  • Adding the four transitions $(q_i, a) to (q_A, a, text{stay})$ for $i in { 1, 2, 3, 4}$ and $a in Gamma$.

$T’$ is still a non-deterministic Turing machine that decides $L$. Moreover, if $w in L$ then $T’$ has at least $4$ accepting paths, therefore $L in mathsf{NP4}$, which concludes the proof.