<ol>
<li>Yes, one can define $BP\Delta_i^P$. Indeed, for any class $\mathcal{C}$ one can define $\mathsf{BP} \cdot \mathcal{C}$ as $L \in \mathsf{BP} \cdot \mathcal{C}$ iff there is a language $L' \in \mathcal{C}$ such that </li>
</ol>

<p>$$ x \in L \Rightarrow (x,y) \in L' \text{ for at least 2/3 of the $y$ of length } \leq poly(x) $$</p>

<p>$$ x \notin L \Rightarrow (x,y) \in L' \text{ for at most 1/3 of the $y$ of length } \leq poly(x) $$</p>

<p>However, generally derandomization does not propagate upwards. For example, $\mathsf{BP \cdot NP} = \mathsf{AM}$, but one needs a stronger assumption (currently) to get $\mathsf{NP} = \mathsf{AM}$ than that (currently) needed to get $\mathsf{P} = \mathsf{BPP}$.</p>

<ol start="2">
<li><p>Seems unlikely. Obviously this would follow if one showed $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$ via a relativizable proof, but we know that no such proof exists. As with (1), I believe the only complexity class equalities I know that propagate upwards (through adding quantifiers) have relativizable (or at least algebraically relativizable) proofs.</p></li>
<li><p>Not that I see right now. For example, if one tries to get a Kabanets-Impagliazzo-style result by reducing to the relativized time hierarchy result that $\mathsf{EXP}^{\mathsf{NP}} \not\subseteq \mathsf{P}^{\mathsf{NP}}$, one doesn't get a contradiction, but instead gets the conclusion (in the middle of the proof, under assumptions) that $\mathsf{EXP}^{\mathsf{NP}} \subseteq \mathsf{\Sigma_2 P}$ which doesn't give the hoped-for contradiction. Other attempts run into the issue that where you want a subexponential $\mathsf{DTIME}$ or $\mathsf{NTIME}$ upper bound to get a contradiction, the best we currently know for $\mathsf{P}^{\mathsf{NP}}$ is that it is in deterministic or nondeterministic exponential time. Maybe with a bit more thought one of the hardness-randomness trade-offs could be made to work though.</p></li>
</ol>

CC BY-SA 4.0
2023-07-08T12:35:55.473Z
"generally derandomization does not propagate upwards" It does not seem to propagate downwards as well, e.g. with $\mathsf{PSPACE}$ oracle.
rus9384
CC BY-SA 3.0
2017-07-11T18:41:06.840Z
2017-07-11T18:41:06.840Z
Joshua Grochow
<p>We know $P\subseteq NP\cap coNP\subseteq\Delta_i^P=P^{\Sigma_{i-1}^P}\subseteq \Sigma_i^P\cap\Pi_i^P=NP^{\Sigma_{i-1}^P}\cap coNP^{\Sigma_{i-1}^P}$.</p>

<ol>
<li><p>If $P=BPP$ is there a 'higher' randomized class analog (call $BP\Delta_i^P$) that will be equal to $\Delta_i^P$ at every $i\in\Bbb N$ and vice versa?</p></li>
<li><p>Does $P=NP\cap coNP\implies\Delta_i^P=\Sigma_i^P\cap\Pi_i^P$ at every $i\in\Bbb N$ (note vice versa need not be true as we have collapse results without $P=NP$)?</p></li>
<li><p>Does $BPP\subseteq\Delta_2^P$ (or hypothetical $BP\Delta_i^P\subseteq\Delta_i^P$) imply any circuit lower bounds?</p></li>
</ol>

<cc.complexity-theory><complexity-classes><lower-bounds><derandomization><polynomial-hierarchy>
On $\Delta_i^P$
Turbo
# On $\Delta_i^P$

(Asked by: username_0 on 2017-07-08)

We know $P\subseteq NP\cap coNP\subseteq\Delta\_i^P=P^{\Sigma\_{i-1}^P}\subseteq \Sigma\_i^P\cap\Pi\_i^P=NP^{\Sigma\_{i-1}^P}\cap coNP^{\Sigma\_{i-1}^P}$.

1. If $P=BPP$ is there a 'higher' randomized class analog (call $BP\Delta\_i^P$) that will be equal to $\Delta\_i^P$ at every $i\in\Bbb N$ and vice versa?
2. Does $P=NP\cap coNP\implies\Delta\_i^P=\Sigma\_i^P\cap\Pi\_i^P$ at every $i\in\Bbb N$ (note vice versa need not be true as we have collapse results without $P=NP$)?
3. Does $BPP\subseteq\Delta\_2^P$ (or hypothetical $BP\Delta\_i^P\subseteq\Delta\_i^P$) imply any circuit lower bounds?

**Tags:** cc.complexity-theory, complexity-classes, lower-bounds, derandomization, polynomial-hierarchy

---

## 1 answers

### Answer by username_1 on 2017-07-11. Score: 1 | Accepted answer

1. Yes, one can define $BP\Delta\_i^P$. Indeed, for any class $\mathcal{C}$ one can define $\mathsf{BP} \cdot \mathcal{C}$ as $L \in \mathsf{BP} \cdot \mathcal{C}$ iff there is a language $L' \in \mathcal{C}$ such that

$$ x \in L \Rightarrow (x,y) \in L' \text{ for at least 2/3 of the $y$ of length } \leq poly(x) $$

$$ x \notin L \Rightarrow (x,y) \in L' \text{ for at most 1/3 of the $y$ of length } \leq poly(x) $$

However, generally derandomization does not propagate upwards. For example, $\mathsf{BP \cdot NP} = \mathsf{AM}$, but one needs a stronger assumption (currently) to get $\mathsf{NP} = \mathsf{AM}$ than that (currently) needed to get $\mathsf{P} = \mathsf{BPP}$.

2. Seems unlikely. Obviously this would follow if one showed $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$ via a relativizable proof, but we know that no such proof exists. As with (1), I believe the only complexity class equalities I know that propagate upwards (through adding quantifiers) have relativizable (or at least algebraically relativizable) proofs.
3. Not that I see right now. For example, if one tries to get a Kabanets-Impagliazzo-style result by reducing to the relativized time hierarchy result that $\mathsf{EXP}^{\mathsf{NP}} \not\subseteq \mathsf{P}^{\mathsf{NP}}$, one doesn't get a contradiction, but instead gets the conclusion (in the middle of the proof, under assumptions) that $\mathsf{EXP}^{\mathsf{NP}} \subseteq \mathsf{\Sigma\_2 P}$ which doesn't give the hoped-for contradiction. Other attempts run into the issue that where you want a subexponential $\mathsf{DTIME}$ or $\mathsf{NTIME}$ upper bound to get a contradiction, the best we currently know for $\mathsf{P}^{\mathsf{NP}}$ is that it is in deterministic or nondeterministic exponential time. Maybe with a bit more thought one of the hardness-randomness trade-offs could be made to work though.

> **Comments:**
> **username_2**: "generally derandomization does not propagate upwards" It does not seem to propagate downwards as well, e.g. with $\mathsf{PSPACE}$ oracle.  

---

