# Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?

Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?

If I understand the polynomial hierarchy correctly, then, if $P = NP$, all complexity classes collapse to one class. Therefore the above two classes should also be equal.

• Can you define $FP^{NP[\log n]}$? Dec 23 '14 at 5:56
• My understanding is that $FP^{NP[\log n]}$ are the function problems solvable in polynomial time using at most $\log n$ queries to an $NP$-oracle. The problem doesn't have much to do with the $PH$ collapsing, the solution is actually much simpler (hint: if $P=NP$, what good is an oracle for $NP$?). Dec 23 '14 at 13:22
• @YuvalFilmus $\mathrm{P}^{\mathrm{NP}[\log n]}$ is "the class of all languages decided by a polynomial-time oracle machine which on input $x$ asks a total of $\mathcal{O}(\log |x|)$ SAT queries" and $\mathrm{FP}^{\mathrm{NP}[\log n]}$ is the corresponding class for functions. (Reference: Papadimitriou, Computational Complexity, 1994) Dec 23 '14 at 15:37
• @TomvanderZanden I guess you want to point out, that if $P = NP$ any call to an oracle for $NP$ has polynomial time (in other words: No oracle is necessary, because it can be "efficiently" be solved). So if $P = NP$, the problems of both classes can be solved in polynomial time (since $\log n$ times calling a polynomial time subprocedure results in polynomial time). Do I understand you correctly? Dec 23 '14 at 15:44

# The reverse

The reverse is true. If $FP^{NP[log]} = FP^{NP}$ then $P = NP$.

You can quickly find this in the Complexity Zoo; It was proven in M. Krentel. The complexity of optimization problems, Journal of Computer and System Sciences 36:490-509, 1988.

# The actual question

The other way around is easier. To quote the definition from Complexity Zoo:

$FP^{NP[log]}$: $FP$ With Logarithmically Many Queries To $NP$

Therefore, if $P = NP$, $FP^{NP[log]} = FP^{P[log]}$. Logarithmically many queries to $P$ is certainly a subset of $NP$, so (if $P = NP$) $FP^{NP[log]} = FP^{NP}$.

• Thank you for your detailed answer. Is it correct to say, that even $P[\log n] = P$ holds since another $\log n$ calls does not effect a problem in $P$? Jan 18 '15 at 20:47
• @John Yes, I think that's correct Jan 18 '15 at 21:10