Question: If $H = \{(G,m)$ $|$ $G$ is a graph with $m$ distinct Hamiltonian cycles $\}$ ($m$ is in binary), prove that $H \in$ polynomial space.My thoughts: I thought that I could show that $H \in NP$, by which it would automatically follow that $H \in$ polynomial space. By the witness theorem, the $m$ distinct Hamiltonian cycles (call them the set $C$) would serve as a witness. However, what is not apparent is if $|C| \leq |G|^k$. In fact, that is the entire problem, isn't it? What am I thinking about wrong over here?
Finding Hamiltonian cycles in polynomial space
graph theory;np