Questão para a prova oral 185
Augusto Jun Devegili (RA 025620)

Quanto ao assunto Problemas NP-Completos, qual a alternativa incorreta?

A)Um problema NP-difícil pode ser também um problema NP-completo
B) A classe de complexidade co-NP é definida pelo conjunto de linguagens cujo complemento esteja em NP-completo
C) Saber se P=NP é um problema em aberto, bem como saber se P = NP interseção co-NP
D) A satisfação de fórmulas booleanas (variáveis boolenas conectadas por AND, OR, NOT, implicação e equivalência, com parênteses) é NP-completa.
E) NDA