Nisan's answer to this [question](https://cstheory.stackexchange.com/questions/562/how-to-produce-a-random-graph-that-does-not-have-a-hamiltonian-cycle/567#567) 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](https://cstheory.stackexchange.com/questions/25103/implications-of-the-impossibility-of-efficient-sampling-from-random-non-hamilton) without answers.



Implications of the impossibility of efficient sampling from random non-Hamiltonian graphs
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”.


