MO417 - Questão para a prova oral

Número: 105

Enunciado:
Considere as seguintes afirmações sobre classes de complexidade:

• NP-Completo ⊂ NP.
• NP ⊂ NP-Completo.
• P ⊂ NP-Completo.
• P ⊂ NP.

Em junho de 2010, quantas das relações acima podiam ser afirmadas com certeza absoluta?

1. 1
2. 2
3. 3
4. 4
5. NDA

Autor: Anderson Francisco Talon