14
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

You can get it here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&rep=rep1&type=pdf

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Jorge Oct 14 '11 at 20:57
  • 1
    $\begingroup$ 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 $\endgroup$ – Jan Johannsen Oct 17 '11 at 9:16
  • 1
    $\begingroup$ 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}}$. $\endgroup$ – Jan Johannsen Oct 17 '11 at 9:27
  • $\begingroup$ Actually, what I am looking is a problem complete for $\mathsf{FP}^{\mathsf{NP}||}$, and I haven't found one yet. $\endgroup$ – Jorge Oct 23 '11 at 23:08

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.