Complexity of "does a directed graph have <=1 Hamiltonian cycles?" I am studying the complexity classes and I am confused what is the complexity of the following problem: &quot;Does a directed graph G has at most 1 Hamiltonian cycle?&quot;
So, from my knowledge and understanding:

Existence of Hamiltonian cycle is a NP(C) problem.
Existence of exactly $k$ ($k&gt;1$) Hamiltonian cycles in a graph belongs to PSPACE.
The stated problem would be a complement of &quot;Does a directed graph G has at least 2 Hamiltonian cycles?&quot;

However, I still fail to see to which class the mentioned problem belongs. Originally I though it would also belong to PSPACE, but not to any space in PSPACE. However, I have consulted my teacher and she said that, while it belongs to PSPACE, it also belongs to some subset of PSPACE. Which subset that would be? Does it belong to co-NP, and the problem from 3. then belongs to NP? If yes, how to prove it (because for now I'm just guessing it based on my teachers' hint)? If no, where does it belong?
Your problem clearly belongs to $\mathsf{co\text{-}NP}$. An easy &quot;no&quot; certificate consists of 2 distinct Hamiltonian cycles. The certificate can clearly be checked in polynomial-time.
The same certificate is also a &quot;yes&quot; certificate for problem in 3 (i.e., &quot;Does a directed graph G has at least 2 Hamiltonian cycles?&quot;), showing that it belongs to $\mathsf{NP}$.