# $\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$

I know that $\mathsf{P}^{\mathsf{NP}[\log n]}$ (logarithmically many calls to the NP oracle) is equivalent to $\mathsf{P}^{\mathsf{NP}||}$ (polynomial number of parallel queries to the NP oracle). I was wondering wether the "function" version of these classes are also equivalent, that is, whether

$$\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$$ If it is known to be true, a pointer would be really helpful.

This is an open problem, it implies $\mathsf{NP} = \mathsf{RP}$ among other things. See the following paper:

Alan Selman. A Taxonomy of Complexity Classes of Functions. Journal of Computer and Systems Sciences 48 (1992), pp. 357-381.

• In that paper they use the class $\mathsf{FP}^{\mathsf{NP}}_{tt}$, can I assume that $\mathsf{FP}^{\mathsf{NP}}_{tt}=\mathsf{FP}^{\mathsf{NP}\|}$? as a side question, is there a prototypical $\mathsf{FP}^{\mathsf{NP}\|}$-complete set? – Jorge Oct 14 '11 at 20:57
• On the side question: Do you mean complete sets for $\mathsf{P}^{\mathsf{NP}||}$? The only natural one I know of is computing the winner in a Dodgson election, see the paper: E. Hemaspaandra, L. Hemaspaandra and J. Rothe. Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Hard for Parallel Access to NP. J.ACM 44 (1997), pp. 214-224 – Jan Johannsen Oct 17 '11 at 9:16
• On the first question: I don't know, but $\mathsf{FP}^{\mathsf{NP}[\log n]} \subseteq \mathsf{FP}_{tt}^{\mathsf{NP}} \subseteq \mathsf{FP}^{\mathsf{NP}||}$, therefore $\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$ implies $\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}_{tt}^{\mathsf{NP}}$. – Jan Johannsen Oct 17 '11 at 9:27
• Actually, what I am looking is a problem complete for $\mathsf{FP}^{\mathsf{NP}||}$, and I haven't found one yet. – Jorge Oct 23 '11 at 23:08