1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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”.

$\endgroup$
2
  • $\begingroup$ Emil, thanks for your answer. Although FP sampling function is an intuitive interpretation, I am interested in efficient sampling in the sense of Nisan's answer. $\endgroup$ Jul 7, 2014 at 18:19
  • $\begingroup$ Nisan’s answer did not give any concrete interpretation, and you did not give one either. The definition in my answer is a best guess at how such a definition might look like. If this is not what you want, you have to be more specific. $\endgroup$ Jul 7, 2014 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.