MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-103

Enunciado: Seja P a classe das linguagens decidíveis em tempo polinomial.  Considere uma linguagem L ∈ P.  Quais dos seguintes fatos sobre uma segunda linguagem M NÃO garantem que M ∈ P?

I - M pode ser reduzida polinomialmente a L.

II - Existe um algoritmo A que, dado um certificado, verifica M em tempo polinomial.

III - Existe um algoritmo A que decide M em tempo polinomial.

IV - A linguagem L pode ser reduzida em tempo polinomial a M.

1. I e IV
2. II, somente.
3. II e IV.
4. IV, somente.
5. N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus