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

CC BY-SA 3.0
2011-05-27T14:23:53.237Z
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
CC BY-SA 3.0
2011-05-27T15:03:35.383Z
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
CC BY-SA 3.0
2011-05-27T12:03:34.037Z
2011-05-27T12:03:34.037Z
Lance Fortnow
<p>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:</p>

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

<p>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".</p>

CC BY-SA 3.0
2011-05-27T17:23:27.813Z
Nice. So there is a strong barrier against showing that there is a derandomization-related barrier to proving PTH.
Sasho Nikolov
CC BY-SA 3.0
2011-05-27T17:07:33.117Z
2011-05-27T17:07:33.117Z
Ryan Williams
<p>In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results? </p>

<p>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?</p>

<p>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.</p>

<p><strong>Some background</strong>: $\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$. </p>

<p>Unconditionally, it is open whether $\mathsf{BPTIME}(n^c) \subseteq \mathsf{BPTIME}(n)$ for all $c &gt; 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 <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aB#bptime">Zoo</a>.</p>

<p>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?</p>

<p><hr>
<strong>EDIT:</strong> I am accepting Ryan's answer as a more complete solution.</p>

<p>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.</p>

<cc.complexity-theory><randomness><derandomization><time-hierarchy>
Hierarchy for BPP vs derandomization
Sasho Nikolov
# Hierarchy for BPP vs derandomization

(Asked by: username_0 on 2011-05-26)

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](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aB#bptime).

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.

**Tags:** cc.complexity-theory, randomness, derandomization, time-hierarchy


---

## 2 answers

### Answer by username_3 on 2011-05-27. Score: 24 | Accepted answer

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".

> **Comments:**
> **username_0**: Nice. So there is a strong barrier against showing that there is a derandomization-related barrier to proving PTH.  

---

### Answer by username_1 on 2011-05-27. Score: 20

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

> **Comments:**
> **username_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?  
> **username_0**: 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?  

---

