<p>Another reason is that this is often without loss of generality, since frequently (though not always - see below) complexity of functions and decision problems are equivalent. Every decision problem can be viewed as a function whose only values are 0 and 1. Conversely, given a function $f$, there are several associated decision problems which usually have the same complexity as $f$, for example:</p>

<ul>
<li>$\{(x,i) : $ the $i$-th bit of $f(x)$ is 1$\}$.</li>
<li>$\{(x,k) : f(x) \leq k\}$ (or $\geq$)</li>
</ul>

<p>Here is an example where the complexity of function classes and their associated language classes seem to differ: $\mathsf{P}^{\mathsf{NP}[\log ]} = \mathsf{P}^{\mathsf{NP}}_{tt}$ [<a href="http://books.google.com/books/about/Log_query_classes.html?id=KRv2twAACAAJ">Wagner 1987 "Log Query Classes"</a>, <a href="http://www.cs.rochester.edu/~lane/lane-thesis-87-840.pdf">Hemaspaandra's 1987 thesis</a>, <a href="http://dx.doi.org/10.1016/0890-5401(91)90075-D">Buss &amp; Hay 1991</a>],  but if $\mathsf{FP}^{\mathsf{NP}[\log ]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$ then $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{P} = \mathsf{UP}$ [<a href="http://dx.doi.org/10.1016/S0022-0000(05)80009-1">Selman 1994</a>]. </p>

<p>(Here the oracle $^{\mathsf{NP}[\log]}$ means the machine gets to make $O(\log n)$ queries to any problem in $\mathsf{NP}$ (say, SAT). The notation $\mathsf{P}^{\mathsf{NP}}_{tt}$ means $\mathsf{P}$ with an $\mathsf{NP}$ oracle, but in which the oracle queries are <em>non-adaptive</em>: on input $x$, the if $y_i$ is the $i$-th string queried to the oracle, then $y_i$ does not depend on the answers to any previous oracle calls. Equivalently, on input $x$ the machine builds a list $y_1, \dotsc, y_m$ without querying the oracle, queries the oracle about all of the $y_i$ and gets the answers, then proceeds to compute without querying the oracle again.)</p>

CC BY-SA 3.0
2013-05-23T22:02:43.840Z
2013-05-23T22:02:43.840Z
Joshua Grochow
<p>Just a piece of the story:</p>

<p>The seminal 1963 paper of <a href="http://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf" rel="nofollow">Hartmanis and Stearns, "On the Computational Complexity of Algorithms"</a>  introduced the definitions of quantified time and space complexity on the multitape Turing
machine model and showed that given more time/space a TM can compute more things.</p>

<blockquote>
... The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence. ...
</blockquote>

<p>Where "sequence" is a generic sequence. Then, when defining a <em>T-computable</em> sequence, they restrict the attention to binary sequences:</p>

<blockquote>
... For the sake of simplicity, we shall talk about binary sequences, 
the generalization being obvious. We use the notation $\alpha = a_1 a_2 ...$
<br>...<br>
The class of <em>T-computable</em> binary sequences shall be denoted bu $S_T$, and we shall
refer to $T(n)$ as a <em>time-function</em>. $S_T$ will be called a complexity class.
</blockquote>

<p>And then in Corollary 2.8:</p>

<blockquote>
... Thus, when considering time-functions greater or equal to $n$,
the slightest increase in operation speed wipes out the distinction between binary and
nonbinary output machines.
</blockquote>

<p>With a backward link to Hilbert and Church / Turing's work on the halting problem:</p>

<blockquote>
Theorem 5. Given a time-function $T$, there is no decision procedure to decide whether a sequence $\alpha$ is in $S_T$ 
</blockquote>

CC BY-SA 3.0
2013-05-23T09:47:23.510Z
2013-05-23T09:54:03.973Z
2013-05-23T09:54:03.973Z
Marzio De Biasi
<p>Complexity theory builds off computability theory, and the typical formulation of problems in computability theory is as decision problems, stemming naturally from setting them up as questions about set membership.</p>

<p>The roots of computability theory go back some way, but if you want the first strong example of a Decision Problem, then Hilbert's <a href="http://en.wikipedia.org/wiki/Entscheidungsproblem">Entscheidungsproblem</a> is the ur example - it is German for "Decision Problem".</p>

CC BY-SA 3.0
2013-05-23T06:37:50.397Z
2013-05-23T06:37:50.397Z
Luke Mathieson
<p>Complexity theory seems to be built around decision problems rather than functions.</p>

<p>Who introduced this first and what is the reason for this choice? </p>

<p>For example, Edmonds' "Paths, trees and flowers" paper is generally credited as the source of the notion of $\mathsf{PTime}$ representing the set of "tractable" problems and this is the path that we have taken.</p>

<cc.complexity-theory><reference-request>
Decision problems vs functions
Thinniyam Srinivasan Ramanatha
# Decision problems vs functions

(Asked by: username_0 on 2013-05-23)

Complexity theory seems to be built around decision problems rather than functions.

Who introduced this first and what is the reason for this choice?

For example, Edmonds' "Paths, trees and flowers" paper is generally credited as the source of the notion of $\mathsf{PTime}$ representing the set of "tractable" problems and this is the path that we have taken.

**Tags:** cc.complexity-theory, reference-request


---

## 3 answers

### Answer by username_1 on 2013-05-23. Score: 7

Another reason is that this is often without loss of generality, since frequently (though not always - see below) complexity of functions and decision problems are equivalent. Every decision problem can be viewed as a function whose only values are 0 and 1. Conversely, given a function $f$, there are several associated decision problems which usually have the same complexity as $f$, for example:

* $\{(x,i) : $ the $i$-th bit of $f(x)$ is 1$\}$.
* $\{(x,k) : f(x) \leq k\}$ (or $\geq$)

Here is an example where the complexity of function classes and their associated language classes seem to differ: $\mathsf{P}^{\mathsf{NP}[\log ]} = \mathsf{P}^{\mathsf{NP}}\_{tt}$ [[Wagner 1987 "Log Query Classes"](http://books.google.com/books/about/Log_query_classes.html?id=KRv2twAACAAJ), [Hemaspaandra's 1987 thesis](http://www.cs.rochester.edu/~lane/lane-thesis-87-840.pdf), [Buss & Hay 1991](http://dx.doi.org/10.1016/0890-5401(91)90075-D)], but if $\mathsf{FP}^{\mathsf{NP}[\log ]} = \mathsf{FP}^{\mathsf{NP}}\_{tt}$ then $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{P} = \mathsf{UP}$ [[Selman 1994](http://dx.doi.org/10.1016/S0022-0000(05)80009-1)].

(Here the oracle $^{\mathsf{NP}[\log]}$ means the machine gets to make $O(\log n)$ queries to any problem in $\mathsf{NP}$ (say, SAT). The notation $\mathsf{P}^{\mathsf{NP}}\_{tt}$ means $\mathsf{P}$ with an $\mathsf{NP}$ oracle, but in which the oracle queries are *non-adaptive*: on input $x$, the if $y\_i$ is the $i$-th string queried to the oracle, then $y\_i$ does not depend on the answers to any previous oracle calls. Equivalently, on input $x$ the machine builds a list $y\_1, \dotsc, y\_m$ without querying the oracle, queries the oracle about all of the $y\_i$ and gets the answers, then proceeds to compute without querying the oracle again.)


---

### Answer by username_3 on 2013-05-23. Score: 5

Complexity theory builds off computability theory, and the typical formulation of problems in computability theory is as decision problems, stemming naturally from setting them up as questions about set membership.

The roots of computability theory go back some way, but if you want the first strong example of a Decision Problem, then Hilbert's [Entscheidungsproblem](http://en.wikipedia.org/wiki/Entscheidungsproblem) is the ur example - it is German for "Decision Problem".


---

### Answer by username_2 on 2013-05-23. Score: 4

Just a piece of the story:

The seminal 1963 paper of [Hartmanis and Stearns, "On the Computational Complexity of Algorithms"](http://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf) introduced the definitions of quantified time and space complexity on the multitape Turing
machine model and showed that given more time/space a TM can compute more things.

> ... The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence. ...

Where "sequence" is a generic sequence. Then, when defining a *T-computable* sequence, they restrict the attention to binary sequences:

> ... For the sake of simplicity, we shall talk about binary sequences,
> the generalization being obvious. We use the notation $\alpha = a\_1 a\_2 ...$
>   
> ...  
> The class of *T-computable* binary sequences shall be denoted bu $S\_T$, and we shall
> refer to $T(n)$ as a *time-function*. $S\_T$ will be called a complexity class.

And then in Corollary 2.8:

> ... Thus, when considering time-functions greater or equal to $n$,
> the slightest increase in operation speed wipes out the distinction between binary and
> nonbinary output machines.

With a backward link to Hilbert and Church / Turing's work on the halting problem:

> Theorem 5. Given a time-function $T$, there is no decision procedure to decide whether a sequence $\alpha$ is in $S\_T$


---

