HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Complement of HAMPATH

Submitted by: @import:stackexchange-cs··
0
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}$

Context

StackExchange Computer Science Q#6128, answer score: 9

Revisions (0)

No revisions yet.