Por que os problemas de decisão são comumente usados ​​na teoria da complexidade?

Da Wikipedia :

O tipo de problema computacional: Os problemas mais comumente usados ​​são os de decisão . No entanto, as classes de complexidade podem ser definidas com base em problemas de função, problemas de contagem, problemas de otimização, problemas de promessa, etc.

Eu também vi as definições de NP-completo, NP-difícil, NP, ..., são definidas apenas para problemas de decisão. Eu me pergunto por que é esse o caso?

É porque qualquer outro problema pode ser convertido equivalentemente em um problema de decisão?

Muitas vezes, problemas de decisão são usados ​​porque permitem uma definição precisa e simples do problema e, como afirmado, muitos outros problemas podem ser convertidos em um problema de decisão equivalente.

Outros tipos de problemas também são considerados na teoria da complexidade, por exemplo, Problemas de Função e Problemas de Pesquisa .

provavelmente existem muitas maneiras diferentes de responder a essa pergunta, mas um elemento-chave é o precedente histórico. a reprovação da existência de um algoritmo para o problema de parada em 1936 por Turing usa o problema de parada como um problema de decisão. por sua vez, isso foi baseado (e resolvido negativamente) por Hilberts Entscheidungsproblem (1928), que solicitava um método sistemático para determinar a verdade ou a falsidade de qualquer afirmação matemática bem formada, isto é, também um problema de decisão.

isso, por sua vez, tem alguma semelhança com o décimo problema de Hilberts, datado de 1900, que pede a solução de equações diofantinas inteiras (muitos de seus 23 problemas de pesquisa de fronteira / pivô foram declarados como problemas de decisão). no entanto, observe o problema de Entscheidung, mesmo enraizado em um conceito muito anterior de Leibniz, como afirma a wikipedia:

A origem do problema de Entscheidung remonta a Gottfried Leibniz, que no século XVII, depois de ter construído uma máquina de cálculo mecânica bem-sucedida, sonhava em construir uma máquina que pudesse manipular símbolos para determinar os valores verdadeiros das declarações matemáticas.

observe também que as equações diofantinas datam dos gregos que foram alguns dos primeiros a considerar, estudar e enfatizar a importância da prova matemática. existem pelo menos dois problemas importantes da teoria dos números, ainda não resolvidos com muitas pesquisas modernas, devido aos gregos: existência de primos gêmeos infinitos e existência de números perfeitos ímpares .

observe alguns "problemas de decisão" (ou seja, na forma de procurar provas para abrir conjecturas matemáticas) literalmente levou centenas de anos para resolver, por exemplo, o último teorema de Fermats , mais de 3,5 séculos, também na teoria dos números.

portanto, os problemas de decisão são muito antigos, mas mesmo que sejam simplesmente declarados, podem ser extremamente difíceis e estão essencialmente enraizados na pergunta "essa afirmação é verdadeira ou falsa" em relação à existência de provas? no coração, é um conceito matemático central. além disso, continua reaparecendo nos lugares modernos de maneira fundamental e reminiscente, como a questão P vs NP (~ 1971), onde a classe NP pode ser definida / estruturada em termos de parada de uma máquina NP e solução do problema de satisfação no tempo P .