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.