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.

  • 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

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
  • $\begingroup$ @John Yes, I think that's correct $\endgroup$ – Apanatshka Jan 18 '15 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.