31

In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results?

A related but vaguer question is: does the existence of a hierarchy for $\mathsf{BPTIME}$ imply any difficult lower bounds? Does the resolution of this problem hit against a known barrier in complexity theory?

My motivation for this question is to understand the relative difficulty (with respect to other major open problems in complexity theory) of showing a hierarchy for $\mathsf{BPTIME}$. I am assuming that everyone believes that such a hierarchy exists, but please correct me if you think otherwise.

Some background: $\mathsf{BPTIME}(f(n))$ contains those languages whose membership can be decided by a probabilistic Turning machine in time $f(n)$ with bounded probability of error. More precisely, a language $L \in \mathsf{BPTIME}(f(n))$ if there exists a probabilistic Turing machine $T$ such that for any $x \in L$ the machine $T$ runs in time $O(f(|x|))$ and accepts with probability at least $2/3$, and for any $x \not \in L$, $T$ runs in time $O(f(|x|))$ and rejects with probability at least $2/3$.

Unconditionally, it is open whether $\mathsf{BPTIME}(n^c) \subseteq \mathsf{BPTIME}(n)$ for all $c > 1$. Barak showed that there exists a strict hierarchy for $\mathsf{BPTIME}$ for machines with $O(\log n)$ advice. Fortnow and Santhanam improved this to 1 bit of advice. This leads me to think that a proving the existence of a probabilistic time hierarchy is not that far off. On the other hand, the result is still open and I cannot find any progress after 2004. References, as usual, can be found in the Zoo.

The relation to derandomization comes from Impagliazzo and Wigderson's results: they showed that under a plausible complexity assumption, $\mathsf{BPTIME}(n^d) \subseteq \mathsf{DTIME}(n^c)$ for any constant $d$ and some constant $c$. By the classical time-hierarchy theorems for deterministic time, this implies a time hierarchy for probabilistic time. I am asking the converse question: does a probabilistic hiearchy hit against a barrier related to proving derandomization results?

EDIT: I am accepting Ryan's answer as a more complete solution.

If anyone has observations about what stands between us and proving the existence of a hierarchy for probabilistic time, feel free to answer/comment. Of course, the obvious answer is that $\mathsf{BPTIME}$ has a semantic definition that defies classical techniques. I am interested in less obvious observations.

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115

2 Answers2

24

Let PTH be the hypothesis that there exists a probabilistic time hierarchy. Suppose the answer to your question is true, i.e., "PTH implies $BPP \subseteq TIME[2^{n^{c}}]$" for some fixed $c$. Then, $EXP \neq BPP$ would be unconditionally true. Consider two cases:

  • If PTH is false, then $EXP \neq BPP$. This is the contrapositive of what Lance noted.
  • If PTH is true, then "PTH implies $BPP \subseteq TIME[2^{n^{c}}]$" so again $EXP \neq BPP$.

In fact, even an infinitely-often derandomization of BPP under PTH would entail $EXP \neq BPP$ unconditionally. So whatever barriers apply to proving $EXP \neq BPP$, they apply to proving statements of the kind "PTH implies derandomization".

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
20

It is not hard to derive a probabilistic time hierarchy if BPP = EXP, the extreme case of no derandomization.

Lance Fortnow
  • 8,681
  • 44
  • 59
  • 2
    And you don't need BPP=EXP, you just need BPP not in DTIME(2^{n^c)}) for a constant c > 1. That is, you only need that BPP is hard for DTIME, not that BPP can solve E-complete languages. This says that extreme lack of derandomization implies a hierarchy. What about intermediate lack of derandomization? – Jeff KInne May 27 '11 at 14:23
  • Good observations. So, a collapse up is just as good as a collapse down to establish a hierarchy. This undermines my motivation, but, technically speaking, isn't it still possible that a probabilistic hierarchy implies derandomization, even though lack of derandomization implies a probabilistic hierarchy (a false statement can imply a true statement)? The vaguer question about what barriers the BPP hierachy problem hits against still stands. E.g. it's possible that BPP has a hierarchy for all oracles (the unresolved question of Fortnow-Sipser'89), so relativization is not a problem afawk? – Sasho Nikolov May 27 '11 at 15:03