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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Related is Aaronson's "On the Equivalence of Sampling and Searching" eccc.weizmann.ac.il/report/2010/128 $\endgroup$
    – usul
    Aug 11, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 1:21

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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$
    – Elle Najt
    Jan 30, 2019 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$
    – Elle Najt
    Jan 31, 2019 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$
    – Elle Najt
    Jan 31, 2019 at 20:27

Your Answer

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

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