Problemas de decisão vs funções

A teoria da complexidade parece ser construída em torno de problemas de decisão e não de funções.

Quem introduziu isso primeiro e qual o motivo dessa escolha?

Por exemplo, o artigo "Caminhos, árvores e flores" de Edmonds é geralmente creditado como a fonte da noção de representando o conjunto de problemas "tratáveis" e esse é o caminho que seguimos.$\mathsf{PTime}$

Outra razão é que isso geralmente ocorre sem perda de generalidade, pois frequentemente (embora nem sempre - veja abaixo) a complexidade de funções e problemas de decisão são equivalentes. Todo problema de decisão pode ser visto como uma função cujos únicos valores são 0 e 1. Por outro lado, dada a função , existem vários problemas de decisão associados que geralmente têm a mesma complexidade que , por exemplo:$f$$f$

• i f ( x ) $\{(x,i) :$ o ésimo bit de é 1 .$i$$f(x)$$\}$
• $\{(x,k) : f(x) \leq k\}$ (ou )$\geq$

Aqui está um exemplo em que a complexidade das classes de função e suas classes de idioma associadas parecem diferir: [ Wagner 1987 "Log Query Classes" , tese de Hemaspaandra em 1987 , Buss & Hay 1991 ], mas se então e [ Selman 1994 ].$\mathsf{P}^{\mathsf{NP}[\log ]} = \mathsf{P}^{\mathsf{NP}}_{tt}$$\mathsf{FP}^{\mathsf{NP}[\log ]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$$\mathsf{NP} = \mathsf{RP}$$\mathsf{P} = \mathsf{UP}$

(Aqui o oracle significa que a máquina pode fazer consultas para qualquer problema em (digamos, SAT). A notação significa com um oracle , mas no qual as consultas do oracle não são adaptáveis : na entrada , se for - th string consultada para o oracle, então não depende das respostas para quaisquer chamadas anteriores do na entrada a máquina cria uma lista O(logn)NP P N P t t PNPxyiiyixy1,…,ymy$^{\mathsf{NP}[\log]}$$O(\log n)$$\mathsf{NP}$$\mathsf{P}^{\mathsf{NP}}_{tt}$$\mathsf{P}$$\mathsf{NP}$$x$$y_i$$i$$y_i$$x$$y_1, \dotsc, y_m$sem consultar o oráculo, consulta o oráculo sobre todos os e obtém as respostas e, depois, calcula sem consultar o oráculo novamente.)$y_i$

A teoria da complexidade constrói a teoria da computabilidade, e a formulação típica de problemas na teoria da computabilidade é como problemas de decisão, decorrente naturalmente de configurá-los como perguntas sobre a associação de conjuntos.

As raízes da teoria da computabilidade remontam de alguma maneira, mas se você deseja o primeiro exemplo forte de um Problema de Decisão, o Entscheidungsproblem de Hilbert é o seu exemplo - é alemão para "Problema de Decisão".

Apenas um pedaço da história:

O artigo seminal de 1963 de Hartmanis e Stearns, "Sobre a complexidade computacional dos algoritmos" introduziu as definições de complexidade quantificada de tempo e espaço no modelo de máquina de Turing multitape e mostrou que, com mais tempo / espaço, uma TM pode calcular mais coisas.

... A complexidade computacional de uma sequência deve ser medida pela rapidez com que uma máquina de Turing multitape pode imprimir os termos da sequência. ...

Onde "sequência" é uma sequência genérica. Então, ao definir uma sequência computável em T , eles restringem a atenção às seqüências binárias:

$\alpha = a_1 a_2 ...$

$S_T$$T(n)$$S_T$

E então no Corolário 2.8:

$n$

Com um link para trás do trabalho de Hilbert e Church / Turing sobre o problema da parada:

$T$$\alpha$$S_T$