MO417 - Quest?o para a prova oral

N?mero: 118

Enunciado:
Considere as seguintes linguagens, onde NPC indica a classe de linguagens NP-completas:
L_x: pertencente à classe P
L_y: pertencente à classe NP
L_z: pertencente à classe NPC

1. L_x e L_y podem ser verificadas em tempo polinomial
2. L_z também pertence a NP, mas pode ou não pertencer a P
3. Se L_x pode ser reduzida a L_z, então L_x pode ser tão dificil quanto L_z
4. Se L_z pode ser reduzida a L_x, então podemos afirmar que P=NP
5. NDA

Autor(a): Matheus Silva Mota