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$ Commented 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$ Commented Jul 7, 2014 at 18:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .