jai

MO417 - QUESTÃO PARA A PROVA ORAL
Número:
Qual é a sequencia correta de passos de um procedimento para provar que uma linguagem L é NP-completo e NP-difícil respectivamente.

1) Escolher uma linguagem L' que seja NP-completa.
2) Descrever um algoritmo que compute uma função F:L'->L, tal que cada instancia x∈{0,1}* de L', F(x)∈L.
3) Provar que o algoritmo computa F em tempo polinomial cada instância.
4) Provar L ∈ NP.
5) Provar que a função F satisfaze x∈L' se e só sem F(x)∈L para todo x∈{0,1}*.

A sequencia correta é:
a. (4,1,2,5,3) e (4,2,5,3)
b. (4,1,2,5,3) e (1,2,5,3)
c. (1,2,3,4,5) e (1,2,3,5)
d. (4,1,2,5) e (4,2,5,3)
e. DNA.

Ideia original de: Vladimir Jaime Rocca Layza