MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-100

Enunciado: Qual das seguintes declarações NÃO é correta?

1. HAM-CYCLE ∈ NP e HAM-CYCLE ∈ NPC.
2. Se L ∈ P, então L ∈ NP.
3. Seja {C_k} uma família de circuitos, onde cada C_k tem k entradas e tamanho Θ(2^k). Então verificar a satisfatibilidade do circuito C_k leva tempo polinomial no número de entradas.
4. Seja L uma linguagem e A um algoritmo que verifica L.  Então para nenhuma string x fora de L existe um certificado y tal que A(x,y)=1. 
5. NDA.

Ideia original de: Armando Faz Hernández