# Non-deterministic version of accepting and deciding

${\bf NP}$ is the class of languages that can be decided in polynomial time by a non-deterministic Turing Machine. Now let ${\bf NP}'$ be the class of languages that can be recognized in polynomial time by a non-deterministic Turing machine.

We can ask the same question: Is ${\bf NP}={\bf NP}'$?

Theorem. ${\bf NP}={\bf NP}'$.

The proof is almost the same, except that we use non-deterministic Turing Machine, instead of deterministic one. For completeness of the detail, I will write the proof.

Proof. Clearly, ${\bf NP} \subseteq {\bf NP}'$. Now, let $L \in {\bf NP}'$. Then there exists a non-deterministic Turing Machine that will accept $x \in L$ in $p(n)$ time, for some polynomial $p$. Now, we construct a non-deterministic Turing Machine $M'$ that will decide $L$ in polynomial time. Let $M'$ on input $x$ runs a simulation of $M(x)$ in $p(n)$ time. If it halts and ACCEPT, then $M'$ also accepts. Otherwise, REJECT. $\square$

Still, the proof is non-constructive.