1
$\begingroup$

I am having difficulty understanding the distinction between NP and Co-NP.

According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language:
HAMPATH = { (G,s,t) | G is a directed graph with a Hamiltonian path from s to t}, there exists a nondeterministic Turing Machine M that can decide this problem in polynomial time. I understood this to mean that for some input (G,s,t), M accepts if G has a Hamiltonian Path from s to t, and M rejects if G does not have a Hamiltonian Path from s to t, both in polynomial time.

However, the book also says that !HAMPATH = { (G,s,t) | G is a directed graph with no Hamiltonian path from s to t} is in Co-NP, so it is not known to be in NP.

Why couldn't the same NTM for HAMPATH be used to decide !HAMPATH, except that it returns the opposite state?

$\endgroup$
1
$\begingroup$

A nondeterministic Turing machine is perhaps more clearly viewed as a Turing machine with two inputs: one is the actual input, in your case $\langle G,s,t \rangle$, and the other a polynomial size "witness", in your case a purported Hamiltonian path $p$. The machine checks, in polynomial time, that $p$ is indeed a Hamiltonian path from $s$ to $t$ in $G$, and if so, accepts; otherwise it rejects.

In what sense does this machine $M$ nondeterministically accept $\mathsf{HAMPATH}$?

  • If $\langle G,s,t \rangle \in \mathsf{HAMPATH}$ then there exists a witness $p$ such that $M(\langle G,s,t \rangle,p)$ accepts.
  • If $\langle G,s,t \rangle \notin \mathsf{HAMPATH}$ then $M(\langle G,s,t \rangle,p)$ rejects for all values of $p$.

Now consider the machine $!M$ which accepts when $M$ rejects and rejects when $M$ accepts.

  • If $\langle G,s,t \rangle \in \mathsf{!HAMPATH}$ then $!M(\langle G,s,t \rangle,p)$ accepts for all values of $p$.
  • If $\langle G,s,t \rangle \notin \mathsf{!HAMPATH}$ then there exists a witness $p$ such that $!M(\langle G,s,t \rangle,p)$ rejects.

As you can see, $!M$ doesn't have the same promises regarding $\mathsf{!HAMPATH}$ that $M$ has regarding $\mathsf{HAMPATH}$.

$\endgroup$
0
$\begingroup$

Nondeterministic can machines have multiple computation paths for each input. The machine accepts if at least one computation path accepts, regardless of how many reject.

So, consider a nondeterministic Turing machine $M$.

  • If all paths on input $x$ accept, then $M$ accepts $x$.
  • If some paths on input $y$ accept, and some reject, then $M$ accepts $y$.
  • If all paths on input $z$ reject, then $M$ rejects $z$.

Now, suppose that we swap the accepting and rejecting states of $M$ to make a new machine, $M'$.

  • All paths on input $x$ reject, so $M'$ rejects $x$.
  • Some paths on input $y$ reject, and some accept, so $M'$ accepts $y$.
  • All paths on input $z$ accept, so $M$ accepts $z$.

So we see that $M'$ doesn't accept the complement of the language accepted by $M$, since both machines accept $y$.

$\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.