If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?
Theorem: For any given $A$, either there are good algorithms to sample every subset of $A$, or what you're describing is impossible.
Proof (perhaps slightly informal): Suppose there are some &quot;problematic&quot; subsets of $A$ (those which cannot be efficiently sampled). Let $C$ be one of those subsets. From the fact that $C$ is problematic, it follows that $|C| \ll |A|$ (otherwise $C$ could be dealt with by rejection-sampling). Now let $B = A \setminus C$. Clearly, rejection-sampling does work on $B$, because $B$ is almost the entirety of $A$. So now we have algorithms for both $A$ and $B$, but no algorithm for $C$. Q.E.D.
Here's a ridiculous example: $A = \{(x_1, x_2, x_3, x_4) \mid x_i \in \mathbb{Z},\; 2 &lt; x_i &lt; 10^{10^{10^{1000}}}\}$ and $B$ contains only those quadruplets of numbers which are not counterexamples to Fermat's Last Theorem (i.e. such that $x_1^{x_4} + x_2^{x_4} \neq x_3^{x_4}$). It's trivially easy to sample $B$, but that gives us no clue whatsoever about how to do $A \setminus B$.