is the class of languages that can be decided in polynomial time by a non-deterministic Turing Machine. Now let 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 ?

**Theorem. **.

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, . Now, let . Then there exists a non-deterministic Turing Machine that will accept in time, for some polynomial . Now, we construct a non-deterministic Turing Machine that will decide in polynomial time. Let on input runs a simulation of in time. If it halts and ACCEPT, then also accepts. Otherwise, REJECT.

Still, the proof is non-constructive.

### Like this:

Like Loading...

Halo kak Raja 😀

Halo Bayu. Apa kabar? 🙂