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