Time complexity of a surjection from natural number to non Hamilton graphs I can build a $O(N)$ surjection from natural numbers to the set of Hamilton graphs with sizes less than $N$. For example, I can first map a natural number $x$ to a pair of numbers $(n, b)$, then $n$ represents the size of the graph, and the binary bits of $b$ represent entries of the adjacency matrix. Then I add necessary entries in the adjacency matrix to connect a cycle: (1--2--3--...--$n$--1). This method defines a surjection because every graph with size less than $N$ has a chance to be generated.
However, it does not seem to work for the complement of the set of Hamilton graphs. I can generate an adjacency matrix as above, but I cannot use $O(N)$ time determine whether the graph is Hamiltonian or not (assuming P $\neq$ NP). Does this exclude the possibility of a ``simple'' surjection (running time is polynomial of $N$)?
 A: Having a polynomial-time surjection from $\mathbb N$ onto the set of non-Hamiltonian graphs would not imply $\textsf P = \textsf {NP}$, but it would have some weaker implications we think are false.
The complexity class $\textsf{NP}$ is the set of all problems for which any yes-instance has a proof, verifiable in polynomial time, of being a yes-instance. Normally, we argue that the Hamiltonian cycle problem is in $\textsf{NP}$ because we can prove a graph is Hamiltonian by giving a description of the Hamiltonian cycle inside it. It is easy for an algorithm to check that such a description really is a Hamiltonian cycle that really is contained in the graph.
Another possible argument for why the Hamiltonian cycle problem is in $\textsf{NP}$, however, is your function. Given a Hamiltonian graph, I can prove it's Hamiltonian by giving two things:

*

*A labeling of the vertices as $1, 2, \dots, n$, so that we can build an adjacency matrix;

*A natural number $x$ such that your Hamiltonian surjection takes $x$ to the same adjacency matrix.

Similarly, if there were a polynomial-time surjection from $\mathbb N$ onto the set of non-Hamiltonian graphs, we could use it to get polynomial-time proofs that a graph is not Hamiltonian! This would prove that the Hamiltonian cycle problem is in the complexity class $\textsf{co-NP}$. Since the Hamiltonian cycle problem is $\textsf{NP}$-complete, this would further imply that $\textsf{NP} = \textsf{co-NP}$.
If $\textsf{P}=\textsf{NP}$, then $\textsf{NP} = \textsf{co-NP}$ as well. Even if $\textsf{P} \ne \textsf{NP}$, it's possible that $\textsf{NP} = \textsf{co-NP}$. However, most researchers believe that $\textsf{P} \ne \textsf{NP}$ and $\textsf{NP} \ne \textsf{co-NP}$.
Conversely, if the Hamiltonian cycle problem were in $\textsf{co-NP}$, then finding the surjection would be easy. Just interpret all inputs $x$ as $\langle a,b\rangle$ where $a$ encodes a graph and $b$ encodes a purported proof that it's not Hamiltonian. The surjection checks the proof, and if it's correct, maps $x$ to $a$. (If the proof is wrong, the surjection outputs some trivial non-Hamiltonian graph like $K_1$.)

For clarity, the difficulty is finding a surjection which is polynomial-time in the  length of the output. (I know this is stated in the question, so I am just emphasizing this for any future readers.) It is easy to find a surjection which is polynomial-time in the length of the input: for example, take the strategy outlined in the previous paragraph, except that $b$ encodes an exponentially long proof.
