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?


1 Answer 1

  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}$.

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

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

  • $\begingroup$ "generally derandomization does not propagate upwards" It does not seem to propagate downwards as well, e.g. with $\mathsf{PSPACE}$ oracle. $\endgroup$
    – rus9384
    Jul 8, 2023 at 12:35

Your Answer

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

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