Enunciado
Escolha a alternativa correta:

A) Um algoritmo de verificação tem complexidade de tempo necessariamente menor que a do problema que ele "verifica".
B) Usando o conhecimento que se tem hoje sobre a classe NPC, sabe-se que o problema de determinar se NÃO há um ciclo hamiltoniano em um grafo é NPC apenas pelo fato deste problema ser Co-NP.
C) Se um problema A se reduz (polinomialmente) a outro B, B é provavelmente mais dificil de solucionar que A, podendo inclusive ser exponencialmente mais difícil.
D) Conhecendo um problema NPC A, para determinar se outro problema B também é NPC é condição necessária e suficiente encontrar uma redução em tempo polinomial de B para A.
E) N.D.A.