The Equivalence of Sampling and Searching
In a sampling problem, we are given an input x?{0,1} n , and asked to sample approximately from a probability distribution \(\mathcal{D}_{x}\) over \(\operatorname{poly} ( n ) \)-bit strings. In a search problem, we are given an input x?{0,1} n , and asked to find a member of a nonempty set A x with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity to show that sampling and search problems are essentially equivalent. More precisely, for any sampling problem S, there exists a search problem R S such that, if \(\mathcal{C}\) is any reasonable complexity class, then R S is in the search version of \(\mathcal{C}\) if and only if S is in the sampling version. What makes this nontrivial is that the same R S works for every\(\mathcal{C}\).
sampling problems search problems kolmogorov complexity algorithmic information theory extended church-turing thesis fbqp function problems quantum computing relational problems