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

<p>The type of problems you want is called <a href="https://en.wikipedia.org/wiki/Search_problem">search problems</a> in complexity theory. For example, see the definition of the complexity class <a href="https://en.wikipedia.org/wiki/FNP_%28complexity%29">FNP</a>. But we still refer to the algorithms solving them simply as algorithms.</p>

<p>There is also the notion of <a href="https://en.wikipedia.org/wiki/Multivalued_function">multifunction</a> which is used in computability, but again it is for problems not algorithms.</p>

CC BY-SA 3.0
2013-07-25T20:11:20.230Z
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: https://complexityzoo.uwaterloo.ca/Complexity_Zoo.
Joshua Grochow
CC BY-SA 3.0
2013-08-19T20:24:04.463Z
"search problems"  a.k.a. "relation problems", where your A(x, y) is a "relation" that must be satisfied.
Andy Drucker
CC BY-SA 3.0
2013-07-25T19:04:43.663Z
2013-07-25T19:10:16.187Z
2013-07-25T19:10:16.187Z
Kaveh
<p>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."</p>

<p>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 <em>some</em> proper vertex-coloring of $G$. We don't care which one.</p>

<p>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.</p>

<p>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.</p>

<p>Thanks!</p>

<cc.complexity-theory>
Algorithms with multiple right answers --- complexity theory terminology
David Harris
# Algorithms with multiple right answers --- complexity theory terminology

(Asked by: username_0 on 2013-07-25)

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!

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2013-07-25. Score: 8 | Accepted answer

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](https://en.wikipedia.org/wiki/Search_problem) in complexity theory. For example, see the definition of the complexity class [FNP](https://en.wikipedia.org/wiki/FNP_%28complexity%29). But we still refer to the algorithms solving them simply as algorithms.

There is also the notion of [multifunction](https://en.wikipedia.org/wiki/Multivalued_function) which is used in computability, but again it is for problems not algorithms.

> **Comments:**
> **username_2**: 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: https://complexityzoo.uwaterloo.ca/Complexity_Zoo.  
> **username_3**: "search problems"  a.k.a. "relation problems", where your A(x, y) is a "relation" that must be satisfied.  

---

