2
$\begingroup$

The Sipser book says, Complement of HAMPATH is not in NP.

I tried to find the solution for this, actually, a rigid proof like HAMPATH, which can state Complement of HAMPATH is in/not in NP, but I could not come up with any.

This is what I think, We are given a path from s to t(which can be a certificate for the problem, or not?), and check if it is not a HAMPATH. But this is easy, we can check this in P time right--Just list down the path, see that if any vertex is repeating in it, or if it is missing any vertex of the graph.

How come we are saying this problem is not in NP

I am very new to P and NP, Please correct my mistakes, and apologies if my question sounds like a silly one.

$\endgroup$
  • $\begingroup$ Yes, a single path can be checked in polynomial time but this is not sufficient to show that there is no Hamilton path in the graph. $\endgroup$ – ttnick Sep 3 at 7:29
  • $\begingroup$ I was looking for this line only!! Thanks a lot. My mistake was, I was taking complement of HAMPATH as: if there is a path from s to t which is not a HAMPATH. But the actual complement is : there is no HAMPATH path from s to t. $\endgroup$ – Shirley Sam Sep 3 at 7:38
3
$\begingroup$

The complement of HAMPATH is the following problem:

Given an undirected graph, determine whether it doesn't contain a Hamiltonian path.

A YES instance for the complement of HAMPATH is a graph which doesn't contain a Hamiltonian path. It is not clear what a witness for this property would be. Contrast that with HAMPATH itself, in which the witness for having a Hamiltonian path is simply a Hamiltonian path.


It is not known whether the complement of HAMPATH is in NP, or equivalently, whether HAMPATH is in coNP.

However, it is considered unlikely that HAMPATH is in coNP, since this would imply that NP=coNP, which is considered unlikely by most researchers in the area.

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