Problema de decisão - Decision problem

Um problema de decisão tem apenas duas saídas possíveis ( sim ou não ) em qualquer entrada.

Na teoria da computabilidade e na teoria da complexidade computacional , um problema de decisão é um problema que pode ser colocado como uma questão sim-não dos valores de entrada. Um exemplo de problema de decisão é decidir se um determinado número natural é primo . Outro é o problema "dado dois números x e y , se x uniformemente dividir y ?". A resposta é 'sim' ou 'não', dependendo dos valores de x e y . Um método para resolver um problema de decisão, fornecido na forma de um algoritmo , é chamado de procedimento de decisão para esse problema. Um procedimento de decisão para o problema de decisão "dado dois números x e y , se x uniformemente dividir y ?" forneceria as etapas para determinar se x divide y uniformemente . Um desses algoritmos é a divisão longa . Se o resto for zero, a resposta é 'sim', caso contrário, é 'não'. Um problema de decisão que pode ser resolvido por um algoritmo é denominado decidível .

Problemas de decisão normalmente aparecem em questões matemáticas de decidibilidade , isto é, a questão da existência de um método eficaz para determinar a existência de algum objeto ou sua participação em um conjunto; alguns dos problemas mais importantes da matemática são indecidíveis .

O campo da complexidade computacional categoriza os problemas de decisão decidíveis de acordo com a sua dificuldade de solução. "Difícil", neste sentido, é descrito em termos dos recursos computacionais necessários ao algoritmo mais eficiente para um determinado problema. O campo da teoria da recursão , por sua vez, categoriza problemas de decisão indecidíveis pelo grau de Turing , que é uma medida da não-computabilidade inerente a qualquer solução.

Definição

Um problema de decisão é uma questão de sim ou não em um conjunto infinito de entradas. É tradicional definir o problema de decisão como o conjunto de entradas possíveis junto com o conjunto de entradas para as quais a resposta é sim .

Essas entradas podem ser números naturais, mas também podem ser valores de algum outro tipo, como strings binárias ou strings sobre algum outro alfabeto . O subconjunto de strings para o qual o problema retorna "sim" é uma linguagem formal e, frequentemente, os problemas de decisão são definidos como linguagens formais.

Usando uma codificação como a numeração de Gödel , qualquer string pode ser codificada como um número natural, por meio do qual um problema de decisão pode ser definido como um subconjunto dos números naturais. Portanto, o algoritmo de um problema de decisão é calcular a função característica de um subconjunto dos números naturais.

Exemplos

Um exemplo clássico de problema de decisão decidível é o conjunto de números primos. É possível decidir efetivamente se um determinado número natural é primo testando todos os possíveis fatores não triviais. Embora métodos muito mais eficientes de teste de primalidade sejam conhecidos, a existência de qualquer método eficaz é suficiente para estabelecer a decidibilidade.

Decidibilidade

Um problema de decisão é decidível ou efetivamente resolvido se o conjunto de entradas (ou números naturais) para o qual a resposta é sim for um conjunto recursivo . Um problema é parcialmente decidível , semidecidível , solucionável ou demonstrável se o conjunto de entradas (ou números naturais) para o qual a resposta for sim um conjunto recursivamente enumerável . Problemas que não são decidíveis são indecidíveis . Para esses não é possível criar um algoritmo, eficiente ou não, que os resolva. ${\ displaystyle A}$

O problema da parada é um importante problema de decisão indecidível; para obter mais exemplos, consulte a lista de problemas indecidíveis .

Problemas completos

Os problemas de decisão podem ser ordenados de acordo com a redutibilidade muitos-um e relacionados a reduções viáveis, como reduções de tempo polinomial . Um problema de decisão P é dito para ser completo para um conjunto de problemas de decisão S , se P é um membro de S e qualquer problema em S pode ser reduzida para P . Problemas de decisão completos são usados ​​na teoria da complexidade computacional para caracterizar classes de complexidade de problemas de decisão. Por exemplo, o problema de satisfatibilidade booleana é completo para a classe NP de problemas de decisão sob redutibilidade em tempo polinomial.

Problemas de função

Os problemas de decisão estão intimamente relacionados aos problemas de função , que podem ter respostas mais complexas do que um simples 'sim' ou 'não'. Um problema de função correspondente é "dado dois números x e y , o que é x dividido por y ?".

Um problema de função consiste em uma função parcial f ; o "problema" informal é calcular os valores de f nas entradas para as quais é definido.

Todo problema de função pode ser transformado em um problema de decisão; o problema de decisão é apenas o gráfico da função associada. (O gráfico de uma função f é o conjunto de pares ( x , y ) tais que f ( x ) = y .) Se esse problema de decisão fosse efetivamente resolvido, o problema da função também o seria. Essa redução, entretanto, não respeita a complexidade computacional. Por exemplo, é possível que o gráfico de uma função seja decidível em tempo polinomial (nesse caso, o tempo de execução é calculado como uma função do par ( x , y )) quando a função não é computável em tempo polinomial (em que caso o tempo de execução é calculado como uma função de x sozinho). A função f ( x ) = 2 ^x possui esta propriedade.

Todo problema de decisão pode ser convertido no problema de função de cálculo da função característica do conjunto associado ao problema de decisão. Se essa função for computável, o problema de decisão associado é decidível. No entanto, essa redução é mais liberal do que a redução padrão usada na complexidade computacional (às vezes chamada de redução muitos-um em tempo polinomial); por exemplo, a complexidade das funções características de um problema NP-completo e seu complemento co-NP-completo é exatamente a mesma, embora os problemas de decisão subjacentes não possam ser considerados equivalentes em alguns modelos típicos de computação.

Problemas de otimização

Ao contrário dos problemas de decisão, para os quais há apenas uma resposta correta para cada entrada, os problemas de otimização estão preocupados em encontrar a melhor resposta para uma determinada entrada. Os problemas de otimização surgem naturalmente em muitas aplicações, como o problema do caixeiro viajante e muitas questões de programação linear .

Existem técnicas padrão para transformar problemas de função e otimização em problemas de decisão. Por exemplo, no problema do caixeiro viajante, o problema de otimização é produzir um passeio com peso mínimo. O problema de decisão associado é: para cada N , para decidir se o gráfico tem qualquer passeio com peso inferior a N . Ao responder repetidamente ao problema de decisão, é possível encontrar o peso mínimo de um passeio.

Como a teoria dos problemas de decisão é muito bem desenvolvida, a pesquisa em teoria da complexidade geralmente se concentra nos problemas de decisão. Os próprios problemas de otimização ainda são de interesse na teoria da computabilidade, bem como em campos como pesquisa operacional .

Veja também

• TODOS (complexidade)
• Problema computacional
• Decidibilidade (lógica) - para o problema de decidir se uma fórmula é uma consequência de uma teoria lógica .
• Problema de pesquisa
• Problema de contagem (complexidade)
• Problema de palavra (matemática)

Referências

• Kozen, DC (2012), Automata and Computability , Springer.
• Hartley Rogers, Jr. , The Theory of Recursive Functions and Effective Computability , MIT Press, ISBN   0-262-68052-1 (brochura), ISBN   0-07-053522-1
• Sipser, M. (1996), Introdução à Teoria da Computação , PWS Publishing Co.
• Robert I. Soare (1987), Recursively Enumerable Sets and Degrees , Springer-Verlag, ISBN   0-387-15299-7
• Daniel Kroening & Ofer Strichman, procedimentos de decisão , Springer, ISBN   978-3-540-74104-6
• Aaron Bradley & Zohar Manna , The calculus of computation , Springer, ISBN   978-3-540-74112-1