# Algorithms with multiple right answers — complexity theory terminology

In standard complexity theory terminology, one wants to find Turing machines which decide membership in a language. For any given string, there is only one right answer --- either "yes" or "no."

But suppose we want a Turing machine $f$, which computes a function of its input $x$. We want to ensure that, for any $x$, we satisfy $A(x, f(x))$ where $A$ is some predicate. For example, given a graph $G$, we want to find some proper vertex-coloring of $G$. We don't care which one.

Many of the standard complexity theory notions have analogues in this model. For example, we may want $f$ to be a deterministic polytime algorithm succeeding with certainty (corresponding to complexity class $P$), we may want $f$ to run in expected polynomial time and succeed with probability $1$ (corresponding to class $ZPP$), we may want $f$ to run polynomial time and succeed with high probability (corresponding to $BPP$), or we may want $f$ to run in deterministic polylog time on polynomial-many parallel processors (corresponding to $NC$). And so forth.

What is the terminology for this type of algorithm? In many cases, we know that there exists some $y$ satisfying $A(x,y)$, so $f$ can't really be said to decide anything. I could just refer to saying that $f$ is an "NC algorithm", which is really an analogy and not proper nomenclature.

Thanks!