Theoretical Computer Science
cc.complexity-theory complexity-classes lower-bounds derandomization polynomial-hierarchy
Updated Fri, 24 Jun 2022 07:12:43 GMT

On $\Delta_i^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}$.

  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?

Solution

  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.


References