Problema de decisão: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 1:
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
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 {{NT|Turing degree|escala de Turing}}, 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. Como explicado anteriormente, na parte em que se fala da equivalência com os problemas de função, não há perda de generalidade.
{{esboço}}
| |||