MO417 - Questão para a prova oral

Número: 2010-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

Ideia original de: Anderson Francisco Talon