Problema de decisão: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 17:
Os '''problemas de decisão''' são problemas de determinar se um determinado elemento de algum universo pertence ou não a um determinado conjunto. Se existir um algoritmo que receba como entrada um elemento ''x'' e retorne como saída 'sim', caso ''x'' pertença ao conjunto ''A'', ou 'não', caso contrário, então diz-se que o problema de decisão para o conjunto ''A'' é '''decidível'''. Do contrário, se não existir um algoritmo capaz de fazer essa avaliação, então diz-se que o problema de decisão para o conjunto ''A'' é '''indecidível'''. Tradicionalmente, é comum definir-se o problema de decisão em termos do conjunto de entradas para as quais o problema retorna 'sim'. Nesse sentido, um problema de decisão é equivalente a uma linguagem formal.
Formalmente, tem-se ainda que um problema de decisão é um subconjunto ''A'' dos números naturais. Usando os números de [[
Um problema de decisão é chamado de '''decidível''' ou '''efetivamente solúvel''' se ''A'' é um [[conjunto recursivo]]. Um problema é chamado '''parcialmente decidível''', '''semi-decidível''', '''solúvel''' ou '''provável''' se ''A'' é um [[conjunto recursivamente enumerável]]. Do contrário, o problema é chamado de '''indecidível'''.
==Exemplos==
Um exemplo clássico de problema de decisão é o conjunto dos números primos. É possível decidir efetivamente se um número natural é primo testando cada possível fator não-trivial.
Embora métodos muito mais eficientes para testar a primalidade de um número sejam conhecidos, a existência de qualquer método é suficiente para estabelecer a decidibilidade.
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.
{{esboço}}
| |||