8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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", Hemaspaandra's 1987 thesis, Buss & Hay 1991], but if $\mathsf{FP}^{\mathsf{NP}[\log ]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$ then $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{P} = \mathsf{UP}$ [Selman 1994].

(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.)

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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 is the ur example - it is German for "Decision Problem".

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Just a piece of the story:

The seminal 1963 paper of Hartmanis and Stearns, "On the Computational Complexity of Algorithms" 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$
| cite | improve this answer | |
$\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.