4
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

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