7
$\begingroup$

Nisan's answer to this question 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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.