$\newcommand{\calC}{\mathcal{C}} \newcommand{\calD}{\mathcal{D}} \newcommand{\calE}{\mathcal{E}}$ I have two questions and the first one is presented in the title. The second one is about the difference between samplable and independently samplable. I think the answer to the second question is similar to the first one, so I will mainly talk about the first in below. (“Independently samplable” means for samplable $\calC, \calD$ over $\{0, 1\}^n$ and $\{0, 1\}^n \times \{0, 1\}^n$ respectively, first sample $y \sim \calC$, then sample $x \sim \calD(\cdot | y)$. i.e., $\calE(x, y) = \calC(y) \calD(x, y) / \sum_v \calD(v, y)$.)

Initially my perspective was: P-computable requires polynomial-length representation, while P-samplable only requires a mapping that maps a certain set of values of (polynomial-length) random bits to an instance $x$, which seems completely constructible from a P-computable.

Later I realized that P-samplable indeed asks for more: the mapping should be efficiently described (that is, not too “complex”), as it is encoded into a randomized Turing machine, with “bounded expressitivity”.

I have long been curious about this. Is my understanding correct, or is there any point I missed?

As for the second question, there might be some choices that make the combination of two “simple” mappings “complex”. (But I failed to find a precise counterexample. Could anybody give one?)

  • $\begingroup$ Please ask only one question per post. If you have multiple questions, each one can be asked separately. Please make sure to put the question in the body of the post. The title helps people know what to expect, but the body should make sense and contain everything relevant. Our site works differently from Quora -- the title is not just the first sentence of your post. $\endgroup$
    – D.W.
    Jan 6 at 9:57


Your Answer

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

Browse other questions tagged or ask your own question.