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.
$\begingroup$
$\endgroup$
-
1$\begingroup$ Can you define $FP^{NP[\log n]}$? $\endgroup$ – Yuval Filmus Dec 23 '14 at 5:56
-
$\begingroup$ 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$?). $\endgroup$ – Tom van der Zanden Dec 23 '14 at 13:22
-
$\begingroup$ @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) $\endgroup$ – John Threepwood Dec 23 '14 at 15:37
-
$\begingroup$ @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? $\endgroup$ – John Threepwood Dec 23 '14 at 15:44
$\begingroup$
$\endgroup$
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}$.
-
$\begingroup$ 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$? $\endgroup$ – John Threepwood Jan 18 '15 at 20:47
-
