Problema de decisão

A 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 computacional que pode ser colocado como uma questão de sim ou não dos valores de entrada. Um exemplo de problema de decisão é decidir por meio de um algoritmo se um determinado número natural é primo. Outro é o problema "dados dois números x e y, x divide igualmente y?& #34;. 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 "dados dois números x e y, x divide igualmente y?" daria as etapas para determinar se x divide igualmente y. 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 é chamado decidível.

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

O campo da complexidade computacional categoriza problemas de decisão decidíveis por quão difíceis eles são de resolver. "Difícil", nesse sentido, é descrito em termos dos recursos computacionais necessários para o 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 juntamente 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 um 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 fatores não triviais possíveis. 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 solucionável 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, solúvel ou provável se o conjunto de entradas (ou números naturais) para o qual a resposta é 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.

O problema da parada é um importante problema de decisão indecidível; para mais exemplos, veja 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 em tempo polinomial. Um problema de decisão P é considerado completo para um conjunto de problemas de decisão S se P é um membro de S e todo problema em S pode ser reduzido a 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 funcionamento

Problemas de decisão estão intimamente relacionados a problemas funcionais, que podem ter respostas mais complexas do que um simples 'sim' ou 'não'. Um problema de função correspondente é "dados 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" é 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) tal que f(x) = y.) Se esse problema de decisão fosse efetivamente solucionável, então o problema de função também seria. No entanto, esta redução não respeita a complexidade computacional. Por exemplo, é possível que o gráfico de uma função seja decidível em tempo polinomial (caso em que 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 (nesse caso, o tempo de execução é calculado como uma função de x sozinha). A função f(x) = 2^x tem essa 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 esta função for computável, então 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 possam não 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 existe apenas uma resposta correta para cada entrada, os problemas de otimização se preocupam em encontrar a melhor resposta para uma determinada entrada. 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 funções e problemas de 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, decidir se o grafo possui algum percurso com peso menor que 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 na teoria da complexidade normalmente 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 a pesquisa operacional.