Enunciado:
Em relação a problemas NP-Completos, qual das alternativas abaixo está CORRETA:

A) Um problema P é dito tratável se ele possui um algoritmo de complexidade polinomial para resolvê-lo, mas não podemos dizer que ele é impossível de ser resolvido caso contrário.

B) A teoria de problemas NP-Completos tem implicações apenas para problemas de decisão.

C) Tanto o problema de caminhos simples mais curtos a partir de uma única origem em um grafo G = (V,E), quanto de caminhos simples mais longos a partir de uma única origem no mesmo grafo G = (V, E), são considerados problema de classe P.

D) Problemas que são resolvidos por algoritmos polinomias não pertecem à classe NP.

E) N.D.A.

Autor: Thiago Alves da Silva