arm

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Qual das seguintes declarações não é correta?

1. HAM-CYCLE ∈ NP e HAM-CYCLE ∈ NPC.
2. Seja L um linguagem e x uma seqüência binaria, então para toda x∉L, não existe um certificado y tal que A(x,y)=1, onde A é um algoritmo que verifica L.
3. Se L∈P, entao L∈NP.
4. Seja C um circuito de k entradas e tamanho θ(2^k), entao verificar a satisfatibilidade do circuito leva tempo polinomial ao numero de entradas.
5. NDA.

Ideia original de: Armando Faz Hernández