Pergunta 9 1. Considere o seguinte enunciado: Sejam A e B dois problemas de decisão. Suponha que seja possível modificar o problema A de tal forma...

Pergunta 9
1. Considere o seguinte enunciado:

Sejam A e B dois problemas de decisão. Suponha que seja possível modificar o problema A de tal forma que ele se comporte como um caso do problema B. Se A é não solucionável, então, como A é um caso de B, conclui-se que B também é não solucionável. Se B é solucionável, então, como A é um caso de B, conclui-se que A também é solucionável.

O enunciado diz respeito à(ao):


a. Princípio da Redução.
b. Hipótese de Turing-Chuch.
c. Problema da Parada.
d. Hierarquia de Chomsky.
e. Teorema da Aproximação.