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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
5
  • 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, 2011 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, 2011 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, 2011 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, 2011 at 23:08
  • $\begingroup$ @JanJohannsen Can you look at the related question cstheory.stackexchange.com/questions/52898/…. Also is $FP_{||}(ZPP)$ contained in $FP_{log}(ZPP)$? $\endgroup$
    – Turbo
    May 29 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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