Why does randomness have stronger effect on reductions than on algorithms?

Question

It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite different effect on polynomial time reductions. By the well known result of Valiant and Vazirani, $SAT$ reduces to $USAT$ via randomized polynomial time reduction. It is not likely that the reduction could be derandomized, since it would yield ${\bf NP}={\bf UP}$, which is thought unlikely.

I wonder, what could be the reason for this asymmetric situation: derandomization seems quite possible in probabilistic polynomial time algorithms, but not in probabilistic polynomial time reductions?

Answer 1

First, let me comment on the specific case of the Valiant-Vazirani reduction; this will, I hope, help clarify the general situation.

The Valiant-Vazirani reduction can be viewed/defined in several ways. This reduction is "trying" to map a satisfiable Boolean formula $F$ to a uniquely-satisfiable $F'$, and an unsatisfiable $F$ to an unsatisfiable $F'$. All output formulas are always obtained by further restricting $F$, so unsatisfiability is always preserved. The reduction can be defined either as outputting a single $F'$, or as outputting a list of $F'_1, \ldots, F'_t$. In the latter case, "success" in the case $F \in SAT$ is defined as having at least one uniquely satisfiable $F'_i$ in the list. Call these two variants the "singleton reduction" and "list-reduction" respectively (this is not standard terminology).

The first point it's important to note is that the success probability in the singleton reduction is quite small, namely $\Theta(1/n)$ where $n$ is the number of variables. The difficulties in improving this success probability are explored in the paper

"Is Valiant-Vazirani's Isolation Probability Improvable?" by Dell et al.

http://eccc.hpi-web.de/report/2011/151/#revision1

In the list-reduction, the success probability can be made large, $1 - 2^{-n}$ say, with a poly$(n)$-sized list. (One can simply repeat the singleton reduction many times, for example.)

Now, it is not at all evident or intuitive that we should be able to directly derandomize a reduction that only has success probability $1/n$. Indeed, none of the hardness-vs-randomness results give hypotheses under which we can do so in this case. It is much more plausible that the list-reduction can be derandomized (with a somewhat larger list). Note though that this would not imply $NP = UP$: our output list of formulas may have many uniquely-satisfiable formulas, and perhaps some with many satisfying assignments, and it seems hopeless to try to define a uniquely-accepting computation over such a list.

Even if we could somehow give a list-reduction in which a satisfiable $F$ always induced a list $F'_1, \ldots, F'_t$ where most of the $F'_j$'s are uniquely satisfiable, there is no clear way to turn that into a deterministic singleton reduction for isolation. The real underlying difficulty is that we don't know of any "approximate-majority operation for uniquely-satisfiable formulas", that is, a reduction $R(F'_1, \ldots, F'_t)$ whose output is uniquely satisfiable if most $F'_j$'s are uniquely satisfiable, and unsatisfiable if most $F'_j$'s are unsatisfiable. This also seems like a general phenomenon: reductions output more complex objects than decision algorithms, and the properties of these objects are harder to check, so it's harder to combine many of these objects into a single object that inherits some property of the majority.

For the Valiant-Vazirani case, it does not even seem likely under plausible derandomization assumptions that we'd be able to obtain $NP = FewP$, that is, to deterministically reduce satisfiable formulas to satisfiable formulas with $\leq$ poly$(n)$ solutions. Intuitively this stems from the fact that the isolating procedure has no idea of even the rough size of the solution set of the formula $F$ it is given.

Answer 2

In the oracle world, it is easy to give examples where randomness gives us much more power. Consider, for example, the problem of finding a zero of a balanced Boolean function. A randomized algorithm accomplishes that using $O(1)$ queries with constant success probability, while any deterministic algorithm requires at least $n/2$ queries.

Here is another situation where it is suspected that randomization helps. Suppose we want to maximize a monotone submodular function over a matroid constraint. There are two different algorithms which give a $1-1/e$ approximation, and this is optimal in this model by a result of Vondrák. Both algorithms need to compute a function of the form $\mathbb{E}_{x \sim X} f(x)$, where $X$ is a distribution with exponential support. Computing this function exactly is too costly, but it can be approximated by sampling, and the result is a randomized algorithm. In contrast, the best known deterministic algorithm, the greedy algorithm, gives a $1/2$ approximation.

A similar situation occurs in unconstrained submodular maximization (here the function is not necessarily monotone). The recent breakthrough algorithm gives an optimal $1/2$ approximation, but its deterministic version gives only a $1/3$ approximation. Here the randomization manifests itself either in exactly the same way as in the monotone case, or (in a different version of the algorithm) by making a few random choices along the way.

One of the authors of the latter paper conjectures that $1/3$ is the best that a deterministic algorithm can achieve, and we can similarly conjecture that $1/2$ is the best that can be achieved in the previous problem. If these conjectures are true, then this is a very natural situation in which randomization provably helps.

Recently, Dobzinski and Vondrák showed how to transform value oracle lower bounds (for randomized algorithms) into hardness results, conditional on NP different from RP (the key ingredient is list decoding). We should mention that the transformation relies on the specific method used to prove the oracle lower bounds. Perhaps it is true that deterministic value oracle lower bounds also translate into hardness results.

Answer 3

A possible reason why it may seem strange to you, that we seem to think there is more apparent (or conjectured) power in the randomized reductions from $\mathsf{NP}$ to $\mathsf{UP}$ than the comparable one from $\mathsf{BPP}$ to $\mathsf P$, is because if we caricature these complexity classes as classes arising from machine models, you may be tempted to think of randomness as something which is either powerful (or not powerful) independently of what machine that facility is added to. — Yet these reductions of different power exist. In fact, a computational resource such as randomness does not necessarily have a fixed amount of computational power, which is either "significant" or "not significant".

We may consider any complexity class which is low for itself — for instance, $\mathsf L$, $\mathsf P$, $\mathsf{BPP}$, $\mathsf{BQP}$, $\mathsf{\oplus P}$, or $\mathsf{PSPACE}$ — to be amenable to a machine model of sorts in which the machine always has a well-defined state about which you can ask questions at any point in time, while also allowing for the computation to continue beyond the question that you ask: in essence, exactly that the machine can simulate one algorithm as a subroutine for another. The machine which performs the computation may not be particularly realistic if we restrict ourselves to practical constraints on resources (e.g. physically realisable and able to produce answers in low-degree polynomial time for problems of interest), but unlike classes such as $\mathsf{NP}$ — for which we have no idea how a nondeterministic machine could produce the answer to another problem in $\mathsf{NP}$ and use the answer in any way aside from a disjunctive truth-table reduction — imagining such a class as being embodied by a machine with a well-defined state which we can enquire into does not lead us badly astray. If we take this position, we can ask what happens if we provide these computational models $\mathsf M$ with extra facilities such as randomness or nondeterminism. (These extra facilities don't necessarily preserve the property of being interpretable by a machine model, especially in the case of nondeterminism, but they do give rise to 'new' classes.) If this extra facility gives the model more power, giving rise to a class $\mathsf C$, this is in effect equivalent to saying that there is a reduction from $\mathsf C$ to $\mathsf M$ using that facility, e.g. a randomized reduction in the case of randomness.

The reason why I'm describing this in terms of classes which are low for themselves is that if we take seriously that they are "possible models of computation in another world", your question about randomized reductions corresponds to the fact that it seems that randomness dramatically increases the power of some models but not others. In place of randomized reductions from $\mathsf{NP}$ to $\mathsf{UP}$, we can observe that there is a randomized reduction from all of $\mathsf{PH}$ to the class $\mathsf{BP\cdot\oplus P}$ — which is obtained if you add bounded-error randomness to $\mathsf{\oplus P}$ — by Toda's Theorem. And your question can then be posed as: why does this happen? Why should some machines gain so much from randomness, and others so little?

In the case of $\mathsf{PH} \subseteq \mathsf{BP\cdot\oplus P}$, it seems as though the modulo-2 nondeterminism entailed in the definition of $\mathsf{\oplus P}$ (essentially a counting quantifier modulo 2) catalyses the randomness entailed in bounded error (essentially a counting quantifier with a promise gap) to give us the equivalent of an entire unbounded hierarchy of existential and universal quantifiers. But this does not mean that we suppose that $\mathsf{\oplus P}$ is itself approximately as powerful as the entire polynomial hierarchy, does it? Neither the resources of bounded-error randomness nor modulo-2 counting are thought to be nearly that powerful. What we observe is that together, these two quantifiers are that powerful. And there's also a question of whether we can really say that randomness is weak in absolute terms, compared say to nondeterminism: if randomness is so weak, and if we're so convinced that $\mathsf{BPP} = \mathsf{P}$, why can we only bound $\mathsf{BPP} \subseteq \Sigma^{\mathsf p}_2 \cap \Delta^{\mathsf p}_2$ in the polynomial hierarchy, using two levels of indeterminism, let alone one? (Aside of course from the fact that it's difficult to prove anything nontrivial in complexity theory; but that again is just the statement that these different sorts of resources are difficult to compare on a scale!)

There is no strong argument that I can give to defend why this should be the case, other than to observe that so far it simply is the case; and that if you think that $\mathsf{PH}$ doesn't collapse, is different from $\mathsf{\oplus P}$, and that $\mathsf{BPP} \approx \mathsf{P}$, then you should consider the possibility that facilities such as randomness and nondeterminism can have powers which are not easily comparable to one another, and which can synergize or catalyse one another to give computational power that neither one would plausibly have on its own. The hypothesis that $\mathsf{BPP} = \mathsf{P}$ is not that "randomness has no power", but that randomness alone (or rather, supplemented only by polynomial time computation and provided to an otherwise deterministic computational model) is not powerful. But this does not mean that there can be no power in randomness.