# Consequences of $P^{NP[o(n)]} = P^{NP}$

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?

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

• 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}$. Mar 15, 2023 at 16:04
• 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. Mar 17, 2023 at 17:34