Problem Detail: Is the complement of the Hamiltonian Path problem known to be in $mathsf{NP}$? I could not find explanations saying that it is, but then neither were there any claims saying that it is not in $mathsf{NP}$.
Asked By : pnp
Answered By : Vor
The HAMPATH complement (“G does not contain an Hamiltonian path from s to t”) is in co-NP; to be more precise it is co-NP complete (it is easy to prove that $L$ is NP-complete if and only if its complement $bar{L}$ is co-NP-complete). The question if it is in NP is open. But since HAMPATH is NP-complete, if its complement is in $mathsf{NP}$ then $mathsf{NP} = mathsf{combox{-}NP}$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6128 Ask a Question Download Related Notes/Documents
