<p>Nisan's answer to this <a href="https://cstheory.stackexchange.com/questions/562/how-to-produce-a-random-graph-that-does-not-have-a-hamiltonian-cycle/567#567">question</a> shows the Impossiblity of efficient sampling from random non-Hamiltonian graphs (unless $NP=coNP$). I am interested in the implications of this conjecture.</p>

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

<p>I am also interested in other complexity implications.</p>

<p>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).</p>

<p>I would be very interested in published works about (preferably efficient) sampling from random non-Hamiltonian graphs (and any possible connection to PCP theorem).</p>

CC BY-SA 3.0
2014-07-06T09:50:46.560Z
Cross-posted to http://mathoverflow.net/questions/173365
Emil Jeřábek
CC BY-SA 3.0
2015-08-09T22:25:21.977Z
@EmilJeřábek Please post your answer from MathOverflow for completeness.
Mohammad Al-Turkistany
<cc.complexity-theory><proof-complexity>
Implications of the impossibility of efficient sampling from random non-Hamiltonian graphs
Mohammad Al-Turkistany
# Implications of the impossibility of efficient sampling from random non-Hamiltonian graphs

(Asked by: username_0 on 2014-07-01)

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 Impossiblity 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).

**Tags:** cc.complexity-theory, proof-complexity

> **Comments:**
> **username_1**: Cross-posted to http://mathoverflow.net/questions/173365  
> **username_0**: @EmilJeřábek Please post your answer from MathOverflow for completeness.  

---

## 0 answers

