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 , 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.