Gabarito rapido

[Joao Meidanis]

Oi Gente,

Ainda nao deu tempo de parar e fazer um gabarito oficial da prova, para
colocar na pagina, mas aqui vao os meus palpites iniciais.

Q1:
3-CNF-SAT e' NP-completa
3-DNF-SAT e' polinomial, portanto nao sabemos se e' NP-completa
3-CNF-TAUT e' polinomial tambem, portanto nao sabemos se e' NP-compl.
3-DNF-TAUT e' completa para co-NP, portanto nao sabemos se e' NPC

Q2:
L2 esta em NP
Algoritmo de verificacao ve^ se esta em L1 uniao L2, depois testa se
esta' em L1 para decidir se esta em L2.

Q3:
Esta' em NP, e' facil testar o caminho dado (certificado)
Reducao de HAM-PATH. Seja G um grafo, Construa <G,n(G)-1>, que esta' em
LONGEST-PATH se e somente se G esta' em HAM-PATH.

Q4:
Ha' uma estrategia vencedora para o primeiro jogador:
x1=1; se x2=0, entao x3=1; se x2=1 entao x3=0

Joao Meidanis IC-UNICAMP
Institute of Computing Av. Albert Einstein, 1251
University of Campinas, Brazil 13083-852, Campinas, Sao Paulo
http://www.ic.unicamp.br/~meidanis Brazil