Proving that a class equals NP ∩ coNP

Question

We say that a non-deterministic Turing machine is nice if for every input x the following holds:
• Every computation path returns either ’accept’, ’reject’ or ’quit’.
• There is at least one non-quit path.
• All non-quit paths have the same value.
Let NICE be the class of all languages L that are accepted by some nice non-deterministic, polynomial time, Truing machine.
Prove that NICE = NP ∩ coNP.

Could you please explain the process of proving that a class is equal to NP ∩ coNP?

Answer 1

Regarding your answer, here are some corrections. For part (1), your argument is partially correct but incorrectly stated. For part (2), your argument is not correct.

Your biggest mistake is in the way you describe nondeterministic Turing machines. Remember that a nondeterministic Turing machine does not magically have access to all possible paths at once -- instead, it nondeterministically picks a path, but at the end it can only follow the particular path it has chosen! So, for example, the language you used in 1.2 "the machine checks if any non-quit path exists" does not make sense.

Similarly, you cannot say this in 1.1: "The machine guesses all the possible paths for the given input." A nondeterministic machine cannot guess all possible paths. It can guess one particular path and then inspect that path.

Instead, you can say this: "the machine guesses one particular path. If that path accepts, accept, otherwise reject."

This correction will also expose an error you made in step (2).

Finally, I suggest that in making this argument, you start by giving the "nice" machine a name, call it N. This will make the logic of the argument much clearer.

You do not need to check 1.3 because you know N is nice; you don't need to verify whether it's nice or not.

Instead, you need to prove that your construction accepts a string iff it is in the language L.

---

Here is a corrected form of your argument (1), incorporating the above. The corrections are in bold:

1. Let us construct an NP machine M for L that gets the input x. Since we know L is accepted by a nice machine, let N be the nice machine for L.

   1.1 The machine M guesses one particular path of N for the given input.

   1.2 The machine M checks the result of N on this path: if it is accept, accept. If it is reject or quit, reject.

   1.3 Let us argue why this construction is correct: first suppose $x \in L$. Then $N$ accepts $x$ on all non-quit paths, therefore $x$ is accepted by at least one path in M, so M accepts. Second, suppose $x \notin L$. Then all paths in M either quit or reject, therefore, all paths in M reject.

---

For part (2), I recommend you start out by naming your variables N, M as in part (1). Then your goal is to define machine M given machine N.

Answer 2

Can I prove the first direction in the following way?

1. Let us construct an NP machine for L that gets the input x.
   1.1 The machine guesses all the possible paths for the given input.
   1.2 The machine checks if any non-quit path exists.
   1.3 The machine checks whether the value of all the 'Accepts' and 'Rejects' paths are equal.
   If both 1.2 and 1.3 are true, then the machine would accept. Otherwise, it would reject.
   The machine is polytime because there are N paths => L∈𝖭𝖯.

2. Let us construct an NP machine for $\overline{L}$ that gets the input x.
   2.1 The machine guesses the value of 'Accept'/'Reject' path T, so that its value will differ from the rest of the 'Accept'/'Reject' paths.
   The machine found a T path successfully, then the machine would accept. Otherwise, the machine would reject.
   => The machine accepts the language $\overline{L}$. The machine is polytime because there are N paths => $\overline{L}$∈𝖭𝖯.
   We proved that L∈𝖭𝖯 and $\overline{L}$∈𝖭𝖯 hence L∈co𝖭𝖯.

Answer 3

Based on the review that I received, I fixed the second part of the proof. I would like to know if it's correct now, I would appreciate your input on this.

2. Let us construct an NP machine M for $\overline{L}$ that gets the input x. Since we know L is accepted by a nice machine, let N be the nice machine for L.

2.1. The machine M guesses one particular path of N for the given input.

2.2. The machine M checks the result of N on this path: if it is rejected or quit, accept. If it is accepted, reject.

2.3. Let us argue why this construction is correct: first suppose 𝑥∈$\overline{L}$. Then all paths in N either quit or reject. Therefore, all paths in M accept. Second, suppose 𝑥∉$\overline{L}$. Then 𝑁 accepts 𝑥 on all non-quit paths, therefore 𝑥 is rejected in M.

2.4. The machine M accepts the language $\overline{L}$.

2.5. The machine M is polytime because there are n paths => $\overline{L}$∈𝖭𝖯.

2.6. We proved that L∈𝖭𝖯 and $\overline{L}$∈𝖭𝖯 hence L∈co𝖭𝖯.