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.

Advertisements

2 thoughts on “Non-deterministic version of accepting and deciding”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s