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

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

<p>You can get it here:
<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&amp;rep=rep1&amp;type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&amp;rep=rep1&amp;type=pdf</a></p>

CC BY-SA 3.0
2011-10-14T20:57:36.177Z
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
CC BY-SA 3.0
2011-10-17T09:16:27.163Z
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
CC BY-SA 3.0
2011-10-17T09:27:03.100Z
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
CC BY-SA 3.0
2011-10-23T23:08:36.733Z
Actually, what I am looking is a problem complete for $\mathsf{FP}^{\mathsf{NP}||}$, and I haven't found one yet.
Jorge
CC BY-SA 4.0
2023-05-29T15:10:53.280Z
@JanJohannsen Can you look at the related question https://cstheory.stackexchange.com/questions/52898/what-is-the-relation-between-these-two-complexity-classes-fl-logzplp-and. Also is $FP_{||}(ZPP)$ contained in $FP_{log}(ZPP)$?
Turbo
CC BY-SA 3.0
2011-10-14T16:47:16.160Z
2011-10-14T16:56:06.503Z
2011-10-14T16:56:06.503Z
Jan Johannsen
<p>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</p>

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

<cc.complexity-theory><complexity-classes>
$\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$
Jorge
# $\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$

(Asked by: username_0 on 2011-10-14)

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.

**Tags:** cc.complexity-theory, complexity-classes

---

## 1 answers

### Answer by username_1 on 2011-10-14. Score: 16

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>

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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  
> **username_1**: 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}}$.  
> **username_0**: Actually, what I am looking is a problem complete for $\mathsf{FP}^{\mathsf{NP}||}$, and I haven't found one yet.  
> **username_2**: @JanJohannsen Can you look at the related question https://cstheory.stackexchange.com/questions/52898/what-is-the-relation-between-these-two-complexity-classes-fl-logzplp-and. Also is $FP_{||}(ZPP)$ contained in $FP_{log}(ZPP)$?  

---

