MO417 - Questão para a prova oral
Número:
Enunciado: Sabendo que dado um problema A e B podemos reduzir A a B se é possível converter a entrada de A para a entrada de B, resolver o problema B e converter a saída de B para o problema A. Isto é, podemos solucionar o problema A através de B. Então sobre a noção de redução e sobre as classes P e NP podemos afirmar que:
a) P ⊂ NP.
b) Um problema pertence à classe NP se seu problema de decisão é tratável.
c) Se B é um problema pertencente à classe P e podemos reduzir A a B então A também pertence à classe P.
d) Se B é um problema pertencente à classe NP e podemos reduzir A a B então A também pertence à classe NP.
e) NDA
Ideia original de: Jacqueline Midlej do Espírito Santo
Enunciado: Sabendo que dado um problema A e B podemos reduzir A a B se é possível converter a entrada de A para a entrada de B, resolver o problema B e converter a saída de B para o problema A. Isto é, podemos solucionar o problema A através de B. Então sobre a noção de redução e sobre as classes P e NP podemos afirmar que:
a) P ⊂ NP.
b) Um problema pertence à classe NP se seu problema de decisão é tratável.
c) Se B é um problema pertencente à classe P e podemos reduzir A a B então A também pertence à classe P.
d) Se B é um problema pertencente à classe NP e podemos reduzir A a B então A também pertence à classe NP.
e) NDA
Ideia original de: Jacqueline Midlej do Espírito Santo
Nenhum comentário:
Postar um comentário