27
$\begingroup$

Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson. But the proof of BPP $=$ P remains still not in sight. The main difficulty seems here to lie in the uniformity: we have one randomized algorithm working for inputs of every dimension (length) $n$, and we want to also find one deterministic algorithm working for inputs of every dimension $n$.

It is long known, at least since Adleman's theorem, that BPP $\subseteq$ P/poly holds in the non-uniform setting (even for algorithms computing functions over infinite domains, like arithmetic circuits working over all real numbers). The disadvantage of these results is, however, that after the derandomizing, we get a sequence of deterministic algorithms, that can be different for inputs from different dimensions $n$.

But if we are unable to show BPP $=$ P in the model of Turing machines, can we at least show this in some restricted uniform, but still "practically relevant" models of computation? One of such models is that of dynamic programming algorithms. At a high (extremely high) level, the model of DP algorithms can be described as follows. We parameterize a given problem $P$ by one (or more) parameters $n$ ("dimension" of inputs), consider the resulting "subproblems" $P_1,P_2,\ldots$ and give one (or more) recurrence equations

$P_n(x)$ = minimum or maximum of some arithmetic combination of the subproblems $P_m(x)$ for $m < n $.

In a randomized DP algorithm, we allow some additional random variables be used as parameters in the recursion equations. Even if very vaguely defined, this model is uniform: we have one DP recurrence for all dimension $n$. But the model is "clearly" much weaker than the (universal) model of Turing machines: no loops, no "crazy" operations - just min or max combined with arithmetic operations.

Question: Is BPP = P known for (at least restricted) DP algorithms?

What, say, about DP algorithms that only use $\min,+$ or $\max,+$ operations in their recursion equations? Actually, I am not aware of any proof of BPP = P in any "non-pathological", at least "somewhat interesting" but uniform model of computation (whatever these "non-pathological" and "somewhat interesting" should mean).

N.B. I have no "stomach feeling" concerning the issue of uniformity in computation. So, any hints/references even to "well-known" results, are welcome.

Note [added 27.11.2017] My question actually is: can we capture THE barrier for derandomization in the uniform setting? After Adleman's theorem, one serious "barrier" for extending it to circuit (or decision trees) working over infinite domains $D$ (like $\mathbb{R}^n$, instead of $\{0,1\}^n$) seemed to lie in the infinity of the domain. Adleman's theorem simulates probabilistic circuits by majority vote of about $\log|D|$ deterministic circuits (Chernoff bounds then suffice). But this (infiniteness of $D$) turned out to be no barrier: it is then enough to replace $\log|D|$ by the Vapnik-Chervonenkis dimension of deterministic circuits.

To be a bit more precise, let ${\cal C}$ be some class of circuit of size at most $t=t(n)$ computing functions $f:\mathbb{R}^n\to \mathbb{R}$. Under a probabilistic circuit of size $t$ I'll mean just a probability distribution $\mathrm{Pr}:{\cal C}\to[0,1]$. Such a "circuit" computes a given function $f:\mathbb{R}^n\to \mathbb{R}$ if $\mathrm{Pr}\{C\in{\cal C}\colon C(x)=f(x)\}\geq 2/3$ holds for every (single) input $x\in \mathbb{R}^n$.

The VC dimension of ${\cal C}$ is the largest natural number $v$ (if there is one) for which there exist $v$ circuits $C_1,\ldots,C_v$ in ${\cal C}$ with the following property:

  • for every $S\subseteq \{1,\ldots,v\}$ there is a point $(x,y)\in \mathbb{R}^n\times \mathbb{R}$ such that $C_i(x)=y$ iff $i\in S$.

The "uniform convergence in probability" results from statistical learning theory yield the tool for derandomization.

Infinite Majority Rule: If a function $f:\mathbb{R}^n\to \mathbb{R}$ can be computed by a probabilistic circuit of size $t(n)$, then $f$ can be computed as a majority vote of $m=O(v)$ deterministic circuits of size $t(n)$, where $v=v(n)$ is the VC dimension of deterministic circuits of size at most $t(n)$.

This rule holds also in the uniform setting: I admittedly used "$t(n)"$ for the size of circuits - this could well be the running time of Turing machines. The reason why this does not show the BPP = P lies in the inherent non-uniformity of what this rule delivers: when the dimension $n$ grows, we are forced to compute majority votes of growing sets of Turing machines.

But this only kills of the VC approach towards resolving the BPP vs. P problem. My hope therefore is that people have tried some "next to pathological" restricted but uniform models to detect THE barrier for derandomization in the uniform setting. I am aware of the connection of BPP vs. P problem with the existence of pseudo-random generators, and similar. But all these results are trying to find the "barrier" in the most general setting, when all Turing machines are in our disposal. What, however, if we "bind hands" of machines - can perhaps then this "uniformity monster" disclose its power? Being unable to derandomize general models of computation, it seems natural to try to detect the uniformity-barrier in restricted models.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.