3
$\begingroup$

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!

$\endgroup$
8
$\begingroup$

I think algorithm is the right word. An algorithm doesn't need to decide or compute a function.

The type of problems you want is called search problems in complexity theory. For example, see the definition of the complexity class FNP. But we still refer to the algorithms solving them simply as algorithms.

There is also the notion of multifunction which is used in computability, but again it is for problems not algorithms.

$\endgroup$
  • 1
    $\begingroup$ See also: TFNP, PPAD, PLS. Also, "multifunctions" have occasionally been used in complexity in regards to functions computed by nondeterministic machines with different outputs on different nondeterministic branches. See NPSV, NPMV in the complexity zoo: complexityzoo.uwaterloo.ca/Complexity_Zoo. $\endgroup$ – Joshua Grochow Jul 25 '13 at 20:11
  • 1
    $\begingroup$ "search problems" a.k.a. "relation problems", where your A(x, y) is a "relation" that must be satisfied. $\endgroup$ – Andy Drucker Aug 19 '13 at 20:24

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.