The “multifunction” version of ZPP?

I would like to ask if there is a name for the class of multifunctions, 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}$, it is not since $\mathsf{ZPP}$ is the class of predicates, and not multifunctions. I really appreciate any pointer to the right sources.

• @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 Mar 3 '11 at 3:23
• @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 Mar 3 '11 at 3:56
• @Dai Le: I think maybe what you're looking for is Las Vegas algorithms, but I'm not sure: 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 Mar 3 '11 at 4:34
• I always thought ZPP was the class of las vegas algorithms – Suresh Venkat Mar 3 '11 at 5:05
• Tsuyoshi has it right above: these should be called ZPP search algorithms (or Las Vegas search algorithms). – Peter Shor Mar 3 '11 at 19:41

1 Answer

I think what you're looking for is Las Vegas algorithms. 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 Tsuyoshi Ito in the comments, $ZPP$ is exactly the class of decision problems decidable in Las Vegas polynomial time.