Questão para a Prova Oral 184
15ª Semana: 16/06/2003 a 20/06/2003
Problemas NP-Completos - Aula 2

Enunciado
Assinale a alternativa que NÃO corresponde a uma propriedade dos problemas NP-Completos.

A) Os problemas que pertencem à classe NP-Completo também pertencem à classe NP.
B) Qualquer problema da classe NP (incluindo os problemas NP-Completos) é redutível a um problema NP Completo.
C) Os problemas que pertencem à classe NP-Completo podem ser resolvidos em tempo polinomial.
D) O caráter NP-Completo se aplica a problemas de decisão, em que a resposta é simplesmente "sim" ou "não" (formalmente, "0" ou "1").
E) N.D.A.

Autora: Camila Ribeiro Rocha
RA: 022247