2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ You prove that every member of the class is in NP, then you prove that every member of the class is in co-NP, then you prove that every problem that is both in NP and co-NP is also in your class. $\endgroup$
    – gnasher729
    Jan 7 at 14:40
  • $\begingroup$ Thank you @gnasher729 $\endgroup$
    – Lioo7
    Jan 7 at 16:04
  • $\begingroup$ How can I prove that every problem that is both in NP and co-NP is also in the class? Can I say that if a problem is in both NP and co-NP, then we can recognize when it's accepted and when it's rejected? So every problem in both NP and co-NP also belongs to our class since we can build a machine with three modes that describe the problem. If the problem is accepted, then it goes to accept. If it is rejected, then it goes to reject or quit. @gnasher729 $\endgroup$
    – Lioo7
    Jan 8 at 15:29

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you so much for your detailed explanation! I have a few questions: 1. Why I do not need to check the value of the paths(1.3) but need to check the result of N? 2. In your correction to 1.3 "Then N accepts 𝑥 on all non-quit paths" did you mean M instead of N? 3. In part 2, can I prove it by showing that NP contains co-L? Or should I use reduction? $\endgroup$
    – Lioo7
    Jan 7 at 18:08
  • 1
    $\begingroup$ 1. You are given that N is nice -- "N is nice" is a given property, not a property you want to show. What you want to show is that your nondeterministic machine accepts the same language $\endgroup$
    – 6005
    Jan 7 at 18:30
  • 2
    $\begingroup$ I recommend carefully writing down (1) what you know and (2) what you want to show. "N is nice" goes under the "what you know" part $\endgroup$
    – 6005
    Jan 7 at 18:30
  • 1
    $\begingroup$ 2. No, this is not an error -- N accepts x on all non-quit paths. M is a nondeterministic machine so it doesn't have quit paths $\endgroup$
    – 6005
    Jan 7 at 18:31
  • 1
    $\begingroup$ 3. Yes, you can prove it by showing that $\overline{L}$ is in NP. $\endgroup$
    – 6005
    Jan 7 at 18:32
0
$\begingroup$

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𝖭𝖯.

$\endgroup$
1
  • $\begingroup$ This is good progress and partially but not fully correct -- I will post an answer with corrections! $\endgroup$
    – 6005
    Jan 7 at 17:14
0
$\begingroup$

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.

  1. 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𝖭𝖯.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.