31
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
24
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Nice. So there is a strong barrier against showing that there is a derandomization-related barrier to proving PTH. $\endgroup$
    – Sasho Nikolov
    May 27, 2011 at 17:23
20
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – Jeff KInne
    May 27, 2011 at 14:23
  • $\begingroup$ 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? $\endgroup$
    – Sasho Nikolov
    May 27, 2011 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.