Problema de decisão

Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não. Por exemplo, o problema: "dados dois números x e y, y é divisível por x?" é um problema de decisão. Ou ainda: "Dado um número inteiro x, x é um número primo?". A resposta para esses problemas pode ser 'sim' ou 'não', e depende dos valores que as variáveis assumem em cada instância do problema. Para a seguinte instância do segundo problema "7 é um número primo?" a resposta é sim, já para a instância "8 é um número primo?" a resposta é não.

Um problema de decisão também pode ser formalizado como o problema de verificar se uma determinada cadeia de caracteres pertence ou não a um conjunto de cadeias de caracteres, também chamado de linguagem formal. O conjunto contém exatamente as cadeias para as quais a resposta à pergunta é 'sim'. Voltando ao exemplo dos números primos proposto anteriormente, pode-se vê-lo também como a linguagem de todas as cadeias no alfabeto {0, 1, 2,..., 9} tal que o inteiro correspondente à cadeia é um número primo.

Problemas de decisão estão intimamente ligados com problemas de função, que podem ter respostas mais complexas do que um simples 'sim' ou 'não'. Um típico problema de função é "dado dois números x e y, para qual x temos que y é divisível por x?". Esses tipos de problema estão relacionados também com os problemas de otimização, os quais se preocupam em achar a melhor solução para um problema particular.

Métodos usados para resolver problemas de decisão são chamados de procedimentos ou algoritmos. Um algoritmo para o problema anterior explicaria em quais situações y é divisível por x, dados x e y. Um problema de decisão que pode ser resolvido por algum algoritmo é chamado de problema de decisão decidível.

O campo de complexidade computacional classifica problemas de decisão decidíveis pelo grau de dificuldade em resolvê-los. "Dificuldade", nesse sentido, é descrito em termos de esforço computacional necessário para o algoritmo mais eficiente para um determinado problema. O campo da teoria da recursão, entretanto, classifica problemas através do grau de insolubilidade da Teoria da Computação e da Complexidade Computacional (no inglês, Turing degree), a qual é uma medida da não-computabilidade inerente a cada solução.

Pesquisas na área da teoria da computabilidade têm focado principalmente nos problemas de decisão.

Definição

Os problemas de decisão são problemas de determinar se um determinado elemento de algum universo pertence ou não a um determinado conjunto (ou equivalentemente, se satisfaz uma determinada propriedade). Se existir um algoritmo que receba como entrada um elemento x e retorne como saída 'sim', caso x pertença ao conjunto A, ou 'não', caso contrário, então diz-se que o problema de decisão para o conjunto A é decidível. Do contrário, se não existir um algoritmo capaz de fazer essa avaliação, então diz-se que o problema de decisão para o conjunto A é indecidível. Tradicionalmente, é comum definir-se o problema de decisão em termos do conjunto de entradas para as quais o problema retorna 'sim'. Nesse sentido, um problema de decisão é equivalente a uma linguagem formal.

Formalmente, tem-se ainda que um problema de decisão é um subconjunto A dos números naturais. Usando a enumeração de Gödel, é possível estudar outros conjuntos, como as linguagens formais. O "problema" informal é decidir quando um dado número está em um determinado conjunto.

Um problema de decisão é chamado de decidível ou efetivamente solúvel se A é um conjunto recursivo. Um problema é chamado parcialmente decidível, semi-decidível, solúvel ou provável se A é um conjunto recursivamente enumerável. Do contrário, o problema é chamado de indecidível.

Exemplos

Um exemplo clássico de problema de decisão é o conjunto dos números primos. É possível decidir efetivamente se um número natural é primo testando cada possível fator não-trivial.

Embora métodos muito mais eficientes para testar a primalidade de um número sejam conhecidos, a existência de qualquer método é suficiente para estabelecer a decidibilidade.

Problemas de decisão indecidíveis importantes incluem o problema da parada. Na teoria da complexidade computacional, problemas de decisão que são completos são usados para caracterizar complexidade de classes de problemas de decisão. Exemplos importantes incluem o problema da satisfabilidade booleana e suas diversas variantes, junto com o problema da alcançabilidade indireta e o problema da alcançabilidade direta.

História

O Entscheidungsproblem, termo alemão para "Problema de decisão", é atribuído a David Hilbert: "Na conferência de 1928 Hilbert fez questões bastante precisas. Primeiro, era a matemática completa... Segundo, era a matemática consistente... E por terceiro, era a matemática decidível? Com isto ele quis dizer: existia um método definitivo que poderia, em princípio ser aplicado a qualquer asserção, e que garantiria a produção correta da decisão nos casos em que a asserção for verdadeira" (Hodges, p. 91). Hilbert acreditava que "em matemática não há ignorabimus" (Hodges, p.91), que no latim significa 'nós não sabemos e não saberemos'.

Equivalência com problemas de função

Um problema de função consiste de uma função parcial f; o "problema" informal é computar os valores de f para as entradas definidas.

Cada problema de função pode ser transformado em um problema de decisão; o problema de decisão é apenas o grafo da função associada. (O grafo da função f é o conjunto de pares (x,y) tais que f(x) = y). Se esse problema de decisão é efetivamente solúvel então o problema de função também o será. Essa redução nao diz respeito à complexidade computacional, no entanto. Por exemplo, é possível que o grafo de uma função seja decidível em tempo polinomial (no caso em que a complexidade algorítmica é computada como uma função do par (x,y)) quando a função não é computável em tempo polinomial (no caso em que a complexidade algorítmica é computada como uma função de x apenas). A função f(x) = 2^x tem essa propriedade.

Cada problema de decisão pode ser convertido em um problema de função de computar a função característica do conjunto associado ao problema de decisão. Se essa função é computável então o problema de decisão associado é decidível. Entretanto, essa redução é mais liberal que a redução padrão utilizada em complexidade computacional. Por exemplo, a complexidade das funções características de um problema NP-completo e seu complement co-NP completo é exatamente a mesma embora o problema de decisão subjacente pode não ser considerado equivalente em alguns modelos típicos da computação.

Referências

Hodges, A., Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for some more history that led to Turing's work.

Hodges references a biography of David Hilbert: Constance Reid, Hilbert (George Allen & Unwin; Springer-Verlag, 1970). There are apparently more recent editions.

Kozen, D.C. (1997), Automata and Computability, Springer.
Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7
Sociedade Brasileira de Matemática Aplicada e Computacional[1]
Computabilidade: os limites da Computação - Regivan H. N. Santiago e Benjamín R. C. Bedregal