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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIs 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.
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 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}$.