Número:
Enunciado: Assinale a alternativa correta:
a) A classificação de problemas em "Problemas de Decisão" e "Problemas de Otimização" é, de certa forma, equivalente à classificação em "Problemas NP" e "Problemas NP-Completos", já que os "Problemas de Decisão" são NP e os problemas de otimização são NP-completos.
b) Seja A um problema de otimização e B um problema de decisão relacionado a A, então se A pertence a NP-Completo implica que B pertence a NP-Completo.
c) Seja A um problem de complexidade desconhecida e seja B um problema NP-Completo. Se encontrarmos uma redução de tempo polinomial que transforma instâncias de A em instâncias de B, então provamos que A também é um problema NP-Completo.
d) Seja A um problema da classe NP e B um problema da classe NP-Completo. Se conseguirmos provar que A não pode ser resolvido em tempo polinomial, então garantiremos que B também não pode.
e) N.D.A
Ideia original de: Danielle Furtado dos Santos Dias
Nenhum comentário:
Postar um comentário