Problema de decisão: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Correção de digitação |
|||
Linha 35:
Um problema de função consiste de uma função parcial ''f''; o "problema" informal é computar os valores de ''f'' para as entradas definidas.
Cada problema de função pode ser transformado em um problema de decisão; o problema de decisão é apenas o [[grafo]] da função associada. (O grafo da função ''f'' é o conjunto de pares (''x'',''y'') tais que ''f''(''x'') = ''y''). Se esse
Cada problema de decisão pode ser convertido em um problema de função de computar a função característica do conjunto associado ao problema de decisão. Se essa função é computável então o problema de decisão associado é decidível. Entretanto, essa redução é mais liberal que a redução padrão utilizada em complexidade computacional. Por exemplo, a complexidade das funções características de um problema NP-completo e seu complement co-NP completo é exatamente a mesma embora o problema de decisão subjacente pode não ser considerado equivalente em alguns modelos típicos da computação.
| |||