# Understanding Hamiltonian Path, NP vs Co-NP

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?

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

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