Two Hamiltonian cycles are different if and only if there is at least one edge they do not share.

Let $L$ consist of all graphs with exactly two Hamiltonian cycles. What complexity class does it belong to?

Let us construct an NTM $M$ that decides $L$ in polynomial time.

Take an NTM $M_1$ that recognizes the existence of a Hamiltonian cycle in polynomial time and run it on $G$. If $M_1$ rejects $G$, reject, otherwise use $M_1$ to construct the cycle $P_1$. Now for each edge $e_i \in P_1$ run $M_1$ on $G_i = (V, E \setminus \{ e_i \})$. If $M_1$ never accepts, reject, otherwise find another Hamiltonian cycle $P_2$ using $M_1$ on any $i$ such that $M_1$ accepts $G_i$. Repeat the same process again but now try every $e_i \in P_1$, $e_j \in P_2$ on $G_{ij} = (V, E \setminus \{ e_i, e_j \})$. If the third Hamiltonian cycle is found, reject, otherwise accept.

Now we can also make $M'$ that decides $\overline{L}$ in polynomial time. We use $M_1$ to see if there is a Hamiltonian cycle - if not, accept, otherwise construct it and use the same process as before to find a second Hamiltonian cycle. If it is not found, then accept, otherwise try to find a third hamiltonian cycle by deleting each pair like before. If the third Hamiltonian cycle was not found, then reject, otherwise accept.

Both $M$ and $M'$ seem to run in polynomial time as they only use $M_1$ but there must be a mistake as this would prove that $\mathcal{NP} = co \textsf{ -} \mathcal{NP}$.

Where is my reasoning wrong and how to decide which complexity class does $L$ belong to?


1 Answer 1


Your $M_1$ is not a polynomial time NTM unless $\mathsf{NP} = \mathsf{coNP}$, I think. In the last step (checking that $G_{ij}$ contains no HC), you essentially want to decide the complement of HC, which is $\mathsf{coNP}$-complete. This is a bit of a tricky thing about nondeterministic computation: you cannot simply invert answers like you can with deterministic computation.

As for the complexity of your problem: Note that it is the intersection of a $\mathsf{NP}$-language (are there at least 2 different HCs) and a $\mathsf{coNP}$-language (does any triple of HCs contain the same HC twice?) and hence in $\mathsf{DP} \subseteq \Delta_2^p$. I don't see an easy way to convincingly argue that it's not contained in some lower class.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.