<p>I think what you're looking for is <a href="http://en.wikipedia.org/wiki/Las_Vegas_algorithm" rel="nofollow">Las Vegas algorithms</a>. I do not know that the class of functions computable by polytime Las Vegas algorithms has an abbreviation beyond "Las Vegas polynomial time". </p>

<p>As pointed out by Tsuyoshi Ito in the comments, $ZPP$ is exactly the class of <em>decision</em> problems decidable in Las Vegas polynomial time.</p>

CC BY-SA 2.5
2011-03-03T21:10:33.327Z
2011-03-03T21:10:33.327Z
Joshua Grochow
<p>I would like to ask if there is a name for the class of <a href="http://en.wikipedia.org/wiki/Multivalued_function" rel="nofollow">multifunctions</a>, each of which can be computed by a probabilistic polytime Turing machine $M$ satisfying the following two conditions:</p>

<ol>
<li>$M$ returns a correct output of the function with high probability</li>
<li>$M$ can either return a correct answer or "don't know", and never return an incorrect answer.</li>
</ol>

<p>Note that although this sounds like <a href="http://en.wikipedia.org/wiki/ZPP_%28complexity%29" rel="nofollow">$\mathsf{ZPP}$</a>, it is not since $\mathsf{ZPP}$ is the class of predicates, and not multifunctions. I really appreciate any pointer to the right sources.</p>

CC BY-SA 2.5
2011-03-03T01:46:32.107Z
Is the output of the multivalued function nonetheless in $\lbrace 0,1 \rbrace$?
Marc Bury
CC BY-SA 2.5
2011-03-03T02:09:52.503Z
No, outputs are binary strings.
Dai Le
CC BY-SA 2.5
2011-03-03T02:30:23.503Z
As I understand it, “multifunction version” is more commonly referred to as “search version,” “relation version” or “function version” (which is a misnomer and potentially confusing) in complexity theory.  Although I do not know any particular paper which discusses the relation version of ZPP, I will be surprised if there is none because the notion seems very natural.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-03T02:32:55.160Z
@Tsuyoshi Ito: I completely agree!
Dai Le
CC BY-SA 2.5
2011-03-03T03:07:13.083Z
@Tsuyoshi Ito or @Dai Le: I don't see the motivation to define a "multifunction version" if I have a "decision version". Perhaps I have missed something in my complexity theory lecture :)
Marc Bury
CC BY-SA 2.5
2011-03-03T03:23:55.720Z
@Marc: Many problems which we care about in the real world are relation problems, not decision problems (we need some answer which is not just yes/no).  On the other hand, restricting our attention to decision problems often makes the arguments in complexity theory (such as reductions) simpler.  Therefore a comparison between decision problems and relation problems is important when it is nontrivial.  Without such a comparison, discussions restricted to decision problems may lose the connection to real-world problems, which is not the end of the world but not a happy thing either.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-03T03:34:45.460Z
@Tsuyoshi Ito: Of course there are non decision problems in the real world but I thought the decision problems and the search problems are [turing equivalent](http://en.wikipedia.org/wiki/Turing_reduction) (not all but all practical problems).
Marc Bury
CC BY-SA 2.5
2011-03-03T03:37:33.023Z
@Marc: in many cases, you can easily reduce function problems to decision problems, so the function version is not really needed. In this case, I don't see how to reduce the defined multifunction problems to ZPP problems.
Dai Le
CC BY-SA 2.5
2011-03-03T03:41:02.053Z
@Marc: That is not a provable claim.  To formulate that claim in a provable form, we need a definition.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-03T03:51:03.107Z
@Tsuyoshi Ito and @Dai Le: Let me suprise :) Perhaps this is a new question but what are the names of the "multifunction version" of $P$, $NP$, $BPP$, $RP$, ...?
Marc Bury
CC BY-SA 2.5
2011-03-03T03:56:29.333Z
@Marc: FP and FNP for the first two. Incidentally, PPAD is an example of a class of problems for which decision is trivial (always YES), but search is nontrivial
Suresh Venkat
CC BY-SA 2.5
2011-03-03T04:34:32.280Z
@Dai Le: I think maybe what you're looking for is Las Vegas algorithms, but I'm not sure: http://en.wikipedia.org/wiki/Las_Vegas_algorithm. I do not know that the class of functions computable by polytime Las Vegas algorithms has an abbreviate beyond "Las Vegas polynomial time".
Joshua Grochow
CC BY-SA 2.5
2011-03-03T05:05:15.947Z
I always thought ZPP was the class of las vegas algorithms
Suresh Venkat
CC BY-SA 2.5
2011-03-03T05:17:06.660Z
@Joshua: "Las Vegas algorithms" seem right! At least, that's how Babai defined Las Vegas algorithms.  "Las Vegas polynomial time" seems like a very reasonable name. Although I don't think you need more points :-), would you like to make it an answer?
Dai Le
CC BY-SA 2.5
2011-03-03T05:49:29.493Z
@Suresh: ZPP is the class of _decision_ problems which have randomized polynomial-time algorithms of Las Vegas type.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-03T19:41:01.743Z
Tsuyoshi has it right above: these should be called ZPP search algorithms (or Las Vegas search algorithms).
Peter Shor 
CC BY-SA 2.5
2011-03-03T19:43:40.930Z
@Suresh: you can model a promise problem within the search version of P, but not, as far as I know, within FP, so I don't see how these classes can be strictly said to be the same.
Peter Shor 
<cc.complexity-theory><reference-request><complexity-classes><terminology>
The "multifunction" version of ZPP?
Dai Le
# The "multifunction" version of ZPP?

(Asked by: username_0 on 2011-03-03)

I would like to ask if there is a name for the class of [multifunctions](http://en.wikipedia.org/wiki/Multivalued_function), each of which can be computed by a probabilistic polytime Turing machine $M$ satisfying the following two conditions:

1. $M$ returns a correct output of the function with high probability
2. $M$ can either return a correct answer or "don't know", and never return an incorrect answer.

Note that although this sounds like [$\mathsf{ZPP}$](http://en.wikipedia.org/wiki/ZPP_%28complexity%29), it is not since $\mathsf{ZPP}$ is the class of predicates, and not multifunctions. I really appreciate any pointer to the right sources.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, terminology

> **Comments:**
> **username_1**: Is the output of the multivalued function nonetheless in $\lbrace 0,1 \rbrace$?  
> **username_0**: No, outputs are binary strings.  
> **username_2**: As I understand it, “multifunction version” is more commonly referred to as “search version,” “relation version” or “function version” (which is a misnomer and potentially confusing) in complexity theory.  Although I do not know any particular paper which discusses the relation version of ZPP, I will be surprised if there is none because the notion seems very natural.  
> **username_0**: @username_2: I completely agree!  
> **username_1**: @username_2 or @username_0: I don't see the motivation to define a "multifunction version" if I have a "decision version". Perhaps I have missed something in my complexity theory lecture :)  
> **username_2**: @Marc: Many problems which we care about in the real world are relation problems, not decision problems (we need some answer which is not just yes/no).  On the other hand, restricting our attention to decision problems often makes the arguments in complexity theory (such as reductions) simpler.  Therefore a comparison between decision problems and relation problems is important when it is nontrivial.  Without such a comparison, discussions restricted to decision problems may lose the connection to real-world problems, which is not the end of the world but not a happy thing either.  
> **username_1**: @username_2: Of course there are non decision problems in the real world but I thought the decision problems and the search problems are [turing equivalent](http://en.wikipedia.org/wiki/Turing_reduction) (not all but all practical problems).  
> **username_0**: @Marc: in many cases, you can easily reduce function problems to decision problems, so the function version is not really needed. In this case, I don't see how to reduce the defined multifunction problems to ZPP problems.  
> **username_2**: @Marc: That is not a provable claim.  To formulate that claim in a provable form, we need a definition.  
> **username_1**: @username_2 and @username_0: Let me suprise :) Perhaps this is a new question but what are the names of the "multifunction version" of $P$, $NP$, $BPP$, $RP$, ...?  
> **username_3**: @Marc: FP and FNP for the first two. Incidentally, PPAD is an example of a class of problems for which decision is trivial (always YES), but search is nontrivial  
> **username_4**: @username_0: I think maybe what you're looking for is Las Vegas algorithms, but I'm not sure: http://en.wikipedia.org/wiki/Las_Vegas_algorithm. I do not know that the class of functions computable by polytime Las Vegas algorithms has an abbreviate beyond "Las Vegas polynomial time".  
> **username_3**: I always thought ZPP was the class of las vegas algorithms  
> **username_0**: @Joshua: "Las Vegas algorithms" seem right! At least, that's how Babai defined Las Vegas algorithms.  "Las Vegas polynomial time" seems like a very reasonable name. Although I don't think you need more points :-), would you like to make it an answer?  
> **username_2**: @Suresh: ZPP is the class of _decision_ problems which have randomized polynomial-time algorithms of Las Vegas type.  
> **username_5**: Tsuyoshi has it right above: these should be called ZPP search algorithms (or Las Vegas search algorithms).  
> **username_5**: @Suresh: you can model a promise problem within the search version of P, but not, as far as I know, within FP, so I don't see how these classes can be strictly said to be the same.  

---

## 1 answers

### Answer by username_4 on 2011-03-03. Score: 7 | Accepted answer

I think what you're looking for is [Las Vegas algorithms](http://en.wikipedia.org/wiki/Las_Vegas_algorithm). I do not know that the class of functions computable by polytime Las Vegas algorithms has an abbreviation beyond "Las Vegas polynomial time".

As pointed out by username_2 in the comments, $ZPP$ is exactly the class of *decision* problems decidable in Las Vegas polynomial time.


---

