Problema de decisão

Origem: Wikipédia, a enciclopédia livre.

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 problem de decisão que pode ser resolvido por algum algoritmo é chamado de probelma 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.

[editar] 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.

[editar] 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.

[editar] 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'.

[editar] 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 proble 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.

[editar] 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