patternMinor
Complement of HAMPATH
Viewed 0 times
complementhampathstackoverflow
Problem
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}$.
Solution
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{co\mbox{-}NP}$
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{co\mbox{-}NP}$
Context
StackExchange Computer Science Q#6128, answer score: 9
Revisions (0)
No revisions yet.