MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-107

Enunciado: Dadas as afirmações abaixo

I. Cada linguagem em NP pode ser decidida em tempo exponencial.
II. Se uma linguagem X for reduzida a uma linguagem NP-difícil, então X  será NP-difícil.
III. Se P é igual a NP, então NP é igual a NP-completo.
IV. A seguinte linguagem está em NP: {n ∈ Naturais | n = p.q, onde p e q são números primos}.


Quantas dessas afirmações são verdadeiras ?

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

Ideia original de: Lucas Miguel de Carvalho