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

<p>The earliest example I can think of is <a href="https://www.sciencedirect.com/science/article/pii/030439758690174X" rel="nofollow noreferrer">JVV86</a> (Thm 5.1), which shows that there is no polynomial-time algorithm to randomly generate a cycle in a directed graph, unless NP=RP.</p>

<p>Similar results along this line are NP-hardness for sampling independent sets, colourings etc. See e.g. <a href="https://epubs.siam.org/doi/10.1137/S0097539701383844" rel="nofollow noreferrer">DFJ02</a>, <a href="https://arxiv.org/abs/1005.5584" rel="nofollow noreferrer">Sly10</a>, <a href="https://dl.acm.org/citation.cfm?doid=2785964" rel="nofollow noreferrer">GSV15</a>. Note that the corresponding search problems are all easy. </p>

<p>The problem can also be defined by "soft" constraints. E.g., sampling from an anti-ferromagnetic Ising model is NP-hard. See <a href="https://epubs.siam.org/doi/10.1137/0222066" rel="nofollow noreferrer">JS93</a> (Thm 14).</p>

<p>Results of this sort are usually stated as NP-hard approximate counting problems, due to the standard self-reductions <a href="https://www.sciencedirect.com/science/article/pii/030439758690174X" rel="nofollow noreferrer">JVV86</a>.</p>

CC BY-SA 4.0
2019-01-30T17:47:32.827Z
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.)
Elle Najt
CC BY-SA 4.0
2019-01-31T20:26:58.163Z
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?
Elle Najt
CC BY-SA 4.0
2019-01-31T20:27:06.813Z
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: https://arxiv.org/pdf/1305.2796.pdf )
Elle Najt
CC BY-SA 4.0
2018-08-13T10:46:30.743Z
2018-08-13T10:46:30.743Z
Heng Guo
<p>I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from. </p>

<p>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$. </p>

<blockquote>
  <p>Q1: Is a reasonable notion of intractable that <em>if</em> 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.)</p>
</blockquote>

<p>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. </p>

<blockquote>
  <p>Q2: What are some more interesting examples of intractable sampling problems than these?</p>
</blockquote>

<p>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$). </p>

<p>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.</p>

CC BY-SA 4.0
2018-08-11T13:27:24.703Z
Related is Aaronson's "On the Equivalence of Sampling and Searching" https://eccc.weizmann.ac.il/report/2010/128/
usul
CC BY-SA 4.0
2018-08-11T19:13:47.070Z
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.
Thomas Steinke
CC BY-SA 4.0
2018-08-12T08:56:49.297Z
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.
Heng Guo
CC BY-SA 4.0
2018-08-12T14:30:25.990Z
@HengGuo I think that would make a decent answer to the question, if you want to post it.
Sasho Nikolov
CC BY-SA 4.0
2018-08-12T16:45:47.740Z
@HengGuo Thanks! Do you have a reference for this?
Elle Najt
CC BY-SA 4.0
2018-08-12T18:15:12.680Z
@Lorenzo That would be this, I think: https://arxiv.org/abs/1005.5584
Clement C.
CC BY-SA 4.0
2018-08-13T01:21:29.870Z
@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 https://www.math.cmu.edu/~af1p/Texfiles/indcount.pdf
Sasho Nikolov
<cc.complexity-theory><randomness><derandomization>
Distributions which are intractable to sample from?
Elle Najt
# Distributions which are intractable to sample from?

(Asked by: username_0 on 2018-08-11)

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.

**Tags:** cc.complexity-theory, randomness, derandomization
> **Comments:**
> **username_1**: Related is Aaronson's "On the Equivalence of Sampling and Searching" https://eccc.weizmann.ac.il/report/2010/128/  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: @HengGuo I think that would make a decent answer to the question, if you want to post it.  
> **username_0**: @HengGuo Thanks! Do you have a reference for this?  
> **username_5**: @Lorenzo That would be this, I think: https://arxiv.org/abs/1005.5584  
> **username_4**: @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 https://www.math.cmu.edu/~af1p/Texfiles/indcount.pdf  

---

## 1 answers

### Answer by username_3 on 2018-08-13. Score: 3 | Accepted answer

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](https://www.sciencedirect.com/science/article/pii/030439758690174X) (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](https://epubs.siam.org/doi/10.1137/S0097539701383844), [Sly10](https://arxiv.org/abs/1005.5584), [GSV15](https://dl.acm.org/citation.cfm?doid=2785964). 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](https://epubs.siam.org/doi/10.1137/0222066) (Thm 14).

Results of this sort are usually stated as NP-hard approximate counting problems, due to the standard self-reductions [JVV86](https://www.sciencedirect.com/science/article/pii/030439758690174X).

> **Comments:**
> **username_0**: 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.)  
> **username_0**: 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?  
> **username_0**: 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: https://arxiv.org/pdf/1305.2796.pdf )  

---

