Questão para a Prova Oral 190

Semana: 16/06/2003 a 20/06/2003

Assunto: NP completude (Parte 2)

Enunciado
Em relação aos problemas NP Completos e aos problemas relacionados, é INCORRETO afirmar:

A) A classe de complexidade NP-Completo é a classe das linguagens L tais que L pertence às classes de complexidade NP e co-NP.
B) A classe de complexidade co-NP é a classe das linguagens L tais que o complemento de L pertence à classe de complexidade NP.
C) A classe de complexidade NP é a classe das linguagens L que podem ser verificadas, a partir de certificados, por um algoritmo de tempo polinomial.
D) A classe de complexidade NP-Difícil é a classe das linguagens L tais que qualquer linguagem pertencente a classe de complexidade NP é redutível em tempo polinomial a L.
E) N.D.A.

Marcelo Fantinato
RA: 000472