MO417 - Questão para a prova oral

Número: 2009-167

Enunciado: A notação A ≤ B entre linguagens significa que A reduz-se polinomialmente a B, ou seja, A é no máximo tão difícil quanto B, a menos de computações polinomiais.  Além disso, a notação A ≤ C, onde C é uma classe, significa que A reduz-se polinomialmente a todas as linguagens em C. Uma definição análoga vale para C ≤ A.
Com base nessas definições, considere as seguintes afirmações:

I) Se A ≤ P e A ≤ B, então B ≤ P.
II) Se A ≤ B e B ≤ P, então A ≤ P.
III) Se A ≤ NP, B ≤ NPC e A puder ser decidida em tempo polinomial, então B também o será.

Escolha a opção correta sobre essas afirmações:

1. Apenas I é verdadeira.
2. Apenas II é verdadeira.
3. Apenas III é verdadeira.
4. I, II e III são verdadeiras.
5. NDA

Ideia original de: Fábio de Souza Azevedo