Implications of the impossibility of efficient sampling from random non-Hamiltonian graphs Nisan's answer to this question shows the Impossibility of efficient sampling from random non-Hamiltonian graphs (unless $NP=coNP$). I am interested in the implications of this conjecture.

Does the Impossibility of efficient sampling from random non-Hamiltonian graphs imply that $NP \ne coNP$?

I am also interested in other complexity implications.
EDIT July 4: My intuition is that efficient sampling from random non-Hamiltonian graphs is possible if and only if $NP=coNP$. It hints a probabilistic characterization of class $NP$ (possibly connected to PCP theorem).
I would be very interested in published works about (preferably efficient) sampling from random non-Hamiltonian graphs (and any possible connection to PCP theorem).
This was originally posted on TCS SE without answers.
 A: You didn’t specify what exactly do you mean by efficient sampling. The following definition will work for my purposes. Let $L$ be a language, and assume for simplicity that $L_n$ (the set of strings in $L$ of length $n$) is nonempty for every $n$. Then $f$ is a sampling function for $L$ if for some polynomial $p(n,m)$:


*

*$f(1^n,1^m,w)\in L_n$ for every $n$, $m$, and $|w|=p(n,m)$,

*$\bigl||L_n|\Pr_{|w|=p(n,m)}(f(1^n,1^m,w)=x)-1\bigr|\le1/m$ for every $n$, $m$, and $x\in L_n$.
(There are other reasonable possibilities for a definition; the conditions here are chosen to be in line with the Noam Nisan’s answer on TCS you linked to, which needs the range of the function to coincide with $L$.)
With the help of Sipser’s coding lemma, every $L\in\mathrm{PH}$ has an approximate counting function $c_L\in\mathrm{FP^{PH}}$ in the sense that $c_L(x,y,1^m)$ computes
$$\bigl|\{z\in L:x\le_\mathrm{Lex}z\le_\mathrm{Lex}y\}\bigr|$$
with relative error $1/m$. One can use this to show that every $L\in\mathrm{PH}$ has a sampling function in $\mathrm{FP^{PH}}$.
In particular, if $\mathrm{NP}=\mathrm{coNP}$, then every PH-language has a sampling function in $\mathrm{FP}^{\mathrm{NP}\cap\mathrm{coNP}}$.
Conversely, if $f$ is a sampling function for $L$, then $L\in\mathrm{NP}^f$. Thus, if $f\in\mathrm{FP}^{\mathrm{NP}\cap\mathrm{coNP}}$, then $L\in\mathrm{NP}$.
So, $\mathrm{NP}=\mathrm{coNP}$ is equivalent to the statement that the language of non-Hamiltonian graphs (or any other coNP-complete language for that matter) has an $\mathrm{FP}^{\mathrm{NP}\cap\mathrm{coNP}}$ sampling function. I see no reason why this should imply the existence of an $\mathrm{FP}$ sampling function, which is presumably what you might mean by “efficient”.
