patternMinor
Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?
Viewed 0 times
cdottruethatlog
Problem
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.
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.
Solution
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}$.
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}$.
Context
StackExchange Computer Science Q#35607, answer score: 5
Revisions (0)
No revisions yet.