I am wondering what the consequences of $\text{P}^{\text{NP}[o(n)]} = \text{P}^{\text{NP}}$ are. Does this imply the collapse of the polynomial hierarchy or contradict something like $\text{ETH}$?

I do know that if $\text{P}^{\text{NP}[k]} = \text{P}^{\text{NP}[k+1]}$ for some constant $k$, then $\text{PH}$ collapses to $\Sigma_3$ [1]. Also, Krentel showed that $\text{FP}^{\text{NP}[log]} = \text{FP}^{NP}$ implies $\text{P} = \text{NP}$ [2]. I guess that a similar argument would show that $\text{FP}^{\text{NP}[o(n)]} = \text{FP}^{\text{NP}}$ contradicts $\text{ETH}$.

Are there any similar results know for decision classes and a non-constant number of queries?

[1]: J. Kadin, The polynomial time hierarchy collapses if the Boolean hierarchy collapses

[2]: M.W. Krentel, The Complexity of Optimization Problems

  • $\begingroup$ I don't know the answer, but will say that in this context sometimes the function and decision versions act somewhat differently. For example, $\mathsf{P}^{\mathsf{NP}[log]} = \mathsf{P}^{\mathsf{NP}}_{tt}$, but Selman showed that if $\mathsf{FP}^{\mathsf{NP}[log]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$ then $\mathsf{NP}=\mathsf{RP}$ and $\mathsf{P}=\mathsf{UP}$. $\endgroup$ Mar 15, 2023 at 16:04
  • $\begingroup$ A quick glance at the proof of Theorem 4.1. in [2] actually confirms your suspicion: if $FP^{NP} \subseteq FP^{NP[o(n)]}$, then there exists a $2^{o(n)}$ algorithm for solving $3SAT$, which contradicts ETH. Indeed (using the notation of [2]) a $2^{o(n)}$-time deterministic algorithm can simulate $M(\varphi)$ for all the possible oracle answers. $\endgroup$ Mar 17, 2023 at 17:34


Your Answer

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