6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Mar 3 '11 at 3:23
  • 2
    $\begingroup$ @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 $\endgroup$ – Suresh Venkat Mar 3 '11 at 3:56
  • 4
    $\begingroup$ @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". $\endgroup$ – Joshua Grochow Mar 3 '11 at 4:34
  • 4
    $\begingroup$ I always thought ZPP was the class of las vegas algorithms $\endgroup$ – Suresh Venkat Mar 3 '11 at 5:05
  • 2
    $\begingroup$ Tsuyoshi has it right above: these should be called ZPP search algorithms (or Las Vegas search algorithms). $\endgroup$ – Peter Shor Mar 3 '11 at 19:41
7
$\begingroup$

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.

$\endgroup$

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.