5
$\begingroup$

I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from.

I'm not sure what the right notion of intractable is, though I know the notion of efficiently samplable: the existence of a polynomial-time randomized Turing machine that can simulate samples from $P$.

Q1: Is a reasonable notion of intractable that if there exists such a randomized Turing machine, it can be derandomized to solve an NP-complete problem? If not, what is the right notion? Is there a good reference for this? (Or just some good search terms.)

There are a lot of tautological examples along the following lines: there is no algorithm to sample from [set of solutions to NP-complete problem union a symbol for no solution], because there is an obvious reduction to [that NP-complete problem] by taking the output of the sampler.

Q2: What are some more interesting examples of intractable sampling problems than these?

There are also examples perhaps like this: Given a set $X$, the goal is to sample uniformly from $P(P(X))$ (powerset). If you could do so with a polynomial time turing machine, you could produce exponentially many bits of entropy in only polynomially many coin flips, which is impossible (because $H(f(Y)) \leq H(Y)$ for any random variable $Y$ and deterministic function $f$).

In order to avoid this kind of example, I want the underlying set of the distribution to grow at most like $2^{p(|x|)}$, where $p$ is a polynomial in the size of the input.

$\endgroup$
  • 1
    $\begingroup$ Related is Aaronson's "On the Equivalence of Sampling and Searching" eccc.weizmann.ac.il/report/2010/128 $\endgroup$ – usul Aug 11 '18 at 13:27
  • 1
    $\begingroup$ Related: Assuming one-way functions exist, generating uniformly random messages with valid digital signatures is hard unless you are given the secret key. Furthermore we can efficiently verify validity without the secret key. $\endgroup$ – Thomas Aug 11 '18 at 19:13
  • 3
    $\begingroup$ There are many NP-hard approximate counting problems satisfying your requirement. E.g. no sampling algorithm exists for uniform independent set in a graph, unless NP=RP. Note that finding an independent set is a trivial task. $\endgroup$ – Heng Guo Aug 12 '18 at 8:56
  • $\begingroup$ @HengGuo I think that would make a decent answer to the question, if you want to post it. $\endgroup$ – Sasho Nikolov Aug 12 '18 at 14:30
  • 1
    $\begingroup$ @ClementC. Sly's result gives the optimal hardness threshold, and shows it's equal to the physics prediction. If you just want hardness of sampling independent sets from some constant degree graph, then this suffices math.cmu.edu/~af1p/Texfiles/indcount.pdf $\endgroup$ – Sasho Nikolov Aug 13 '18 at 1:21
3
$\begingroup$

I'll expand my comment to an answer. Many combinatorial structures in graphs are actually NP-hard to sample from.

The earliest example I can think of is JVV86 (Thm 5.1), which shows that there is no polynomial-time algorithm to randomly generate a cycle in a directed graph, unless NP=RP.

Similar results along this line are NP-hardness for sampling independent sets, colourings etc. See e.g. DFJ02, Sly10, GSV15. Note that the corresponding search problems are all easy.

The problem can also be defined by "soft" constraints. E.g., sampling from an anti-ferromagnetic Ising model is NP-hard. See JS93 (Thm 14).

Results of this sort are usually stated as NP-hard approximate counting problems, due to the standard self-reductions JVV86.

$\endgroup$
  • $\begingroup$ This answer was very useful, so thank you very much for it! I have one further question: Is there a word analogous to "NP-complete" for describe sampling problems so that efficient solutions would imply $RP = NP$? (In cases that are not self-reducible.) $\endgroup$ – Lorenzo Jan 30 at 17:47
  • $\begingroup$ I have another question: It seems like a feature of these kinds of arguments that we replace certain substructure by substructures of increased complexity (e.g. edges by chains of diamonds), thereby pumping up the probability of the sampler selecting witnesses for NP complete problems. This is useful for saying that there are no samplers that work on very general classes of input graphs, but if we want to insist on more local uniformity, are there any results or methods that work? $\endgroup$ – Lorenzo Jan 31 at 20:26
  • $\begingroup$ For example, are there any sampling problems that are known to be intractable if the input graph is a simply connected polyomino?(I know this class is rich enough to support $NP$-complete problems: arxiv.org/pdf/1305.2796.pdf ) $\endgroup$ – Lorenzo Jan 31 at 20:27

Your Answer

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

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