<p>I am wondering what the consequences of <span class="math-container">$\text{P}^{\text{NP}[o(n)]} = \text{P}^{\text{NP}}$</span> are. Does this imply the collapse of the polynomial hierarchy or contradict something like <span class="math-container">$\text{ETH}$</span>?</p>
<p>I do know that if <span class="math-container">$\text{P}^{\text{NP}[k]} = \text{P}^{\text{NP}[k+1]}$</span> for some constant <span class="math-container">$k$</span>, then <span class="math-container">$\text{PH}$</span> collapses to <span class="math-container">$\Sigma_3$</span> [1].
Also, Krentel showed that <span class="math-container">$\text{FP}^{\text{NP}[log]} = \text{FP}^{NP}$</span> implies <span class="math-container">$\text{P} = \text{NP}$</span> [2]. I guess that a similar argument would show that <span class="math-container">$\text{FP}^{\text{NP}[o(n)]} = \text{FP}^{\text{NP}}$</span> contradicts <span class="math-container">$\text{ETH}$</span>.</p>
<p>Are there any similar results know for decision classes and a non-constant number of queries?</p>
<p>[1]: J. Kadin, <a href="https://epubs.siam.org/doi/pdf/10.1137/0217080" rel="noreferrer">The polynomial time hierarchy collapses if the Boolean hierarchy collapses</a></p>
<p>[2]: M.W. Krentel, <a href="https://reader.elsevier.com/reader/sd/pii/0022000088900396?token=CA83F146F6EC71559B3D86C7C025EB0F7697E054451570DD8D182B4BFFC6E6CC28CF2DB8D275085F854360AE99F17EE8&amp;originRegion=eu-west-1&amp;originCreation=20230315100949" rel="noreferrer">The Complexity of Optimization Problems</a></p>

CC BY-SA 4.0
2023-03-15T16:04:31.220Z
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](https://doi.org/10.1016/S0022-0000(05)80009-1) showed that if $\mathsf{FP}^{\mathsf{NP}[log]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$ then $\mathsf{NP}=\mathsf{RP}$ and $\mathsf{P}=\mathsf{UP}$.
Joshua Grochow
CC BY-SA 4.0
2023-03-17T17:34:30.840Z
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.
Reijo Jaakkola
<cc.complexity-theory><complexity-classes>
Consequences of $P^{NP[o(n)]} = P^{NP}$
user68775
# Consequences of $P^{NP[o(n)]} = P^{NP}$

(Asked by: username_0 on 2023-03-15)

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](https://epubs.siam.org/doi/pdf/10.1137/0217080)

[2]: M.W. Krentel, [The Complexity of Optimization Problems](https://reader.elsevier.com/reader/sd/pii/0022000088900396?token=CA83F146F6EC71559B3D86C7C025EB0F7697E054451570DD8D182B4BFFC6E6CC28CF2DB8D275085F854360AE99F17EE8&originRegion=eu-west-1&originCreation=20230315100949)

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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](https://doi.org/10.1016/S0022-0000(05)80009-1) showed that if $\mathsf{FP}^{\mathsf{NP}[log]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$ then $\mathsf{NP}=\mathsf{RP}$ and $\mathsf{P}=\mathsf{UP}$.  
> **username_2**: 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.  

---

## 0 answers

