Problema de decisão: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 3:
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 do [[grau de
insolubilidade da Teoria da Computação e da Complexidade Computacional]] (no inglês, ''Turing degree''),
Pesquisas na área da teoria da computabilidade têm focado principalmente nos problemas de decisão.
Linha 27 ⟶ 26:
Problemas de decisão indecidíveis importantes incluem o problema da parada. Na teoria da complexidade computacional, problemas de decisão que são completos são usados para caracterizar complexidade de classes de problemas de decisão. Exemplos importantes incluem o problema da satisfabilidade booleana e suas diversas variantes, junto com o problema da alcançabilidade indireta e o problema da alcançabilidade direta.
== História ==
O ''[[Entscheidungsproblem]]'', termo alemão para "Problema de decisão", é atribuído a [[David Hilbert]]: "Na conferência de 1928 Hilbert fez questões bastante precisas. Primeiro, era a matemática ''completa''... Segundo, era a matemática ''consistente''... E por terceiro, era a matemática ''decidível''? Com isto ele quis dizer: existia um método definitivo que poderia, em princípio ser aplicado a qualquer asserção, e que garantiria a produção correta da decisão nos casos em que a asserção for verdadeira" (Hodges, p. 91). Hilbert acreditava que "em matemática não há ''ignorabimus''" (Hodges, p.91), que no latim significa 'nós não sabemos e não saberemos'.
==Equivalência com problemas de função==
A [[function problem]] consists of a partial function ''f''; the informal "problem" is to compute the values of ''f'' on the inputs for which it is defined.
Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. (The graph of a function ''f'' is the set of pairs (''x'',''y'') such that ''f''(''x'') = ''y''.) If this decision problem were effectively solvable then the function problem would be as well. This reduction does not respect computational complexity, however. For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair (''x'',''y'') ) when the function is not computable in polynomial time (in which case running time is computed as a function of ''x'' alone). The function ''f''(''x'') = ''2''<sup>''x''</sup> has this property.
Every decision problem can be converted into the function problem of computing the [[indicator function|characteristic function]] of the set associated to the decision problem. If this function is computable then the associated decision problem is decidable. However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial-time many-one reduction); for example, the complexity of the characteristic functions of an NP-complete problem and its co-NP complete complement is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.
{{esboço}}
[[Categoria:Lógica]]
[[Categoria:Teoria da Computação]]
[[de:Entscheidungsproblem]]
| |||