Sumários
Correcção TESTE 1
13 abril 2011, 14:00 • José Félix Costa
Nesta aula, resolveu-se o TESTE 1.
Discutiram-se detalhes da prova de que COMPOSITES in NP. Abordou-se a natureza das provas de PRIMES in NP e de PRIMES in P.
+++++++++++++++++++++++++++++++++++++++++++++++++++++
TPC:
Suponha que certo conjunto A é tal que ambos A e A pertencem a NP (e.g., PRIMES e COMPOSITES). Suponha agora que se prova que A é NP-completo. Qual é a consequência?
Técnicas de redução I
12 abril 2011, 10:00 • José Félix Costa
Redução de muitos para um em tempo polinomial
Conceito.
Conjuntos difíceis e conjuntos completos para uma classe.
Graus-m polinomiais.
Fecho de P, NP, co-NP e PSPACE para a redução. Uso do resultado em certas demonstrações.
NP-completude de SAT, CNF-SAT e CLIQUE. PSPACE-completude de QBF. NLOG-completude de REACHABILITY.
Fórmulas
11 abril 2011, 10:00 • José Félix Costa
Fórmulas booleanas: variáveis, fórmulas booleanas, fórmulas booleanas quantificadas.
Substituições de variáveis. Atribuições de valores. Validade de uma fórmula.
Contagem de atribuições, construção de fórmula sobre um conjunto de n variáveis que é satisfeita por exactamente 0 < i < 2^n atribuições de valor.
Equivalência de fórmulas booleanas. Equivalências mais notáveis.
Literal, cláusula, forma normal conjuntiva.
Codificação de fórmulas booleanas.
Principais conjuntos: (a) SAT --- conjunto dos códigos das fórmulas booleanas válidas, (b) CNF-SAT --- conjunto dos códigos das fórmulas booleanas na forma normal conjuntiva válidas, (c) QBF --- conjunto dos códigos das fórmulas booleanas quantificadas fechadas às quais corresponde o valor de verdade.
Técnica da redução
5 abril 2011, 10:00 • José Félix Costa
Redução de muitos para um em tempo polinomial.
Conjuntos difíceis e conjuntos completos para uma classe.
+++++++++++++++++++++++++++++++++++++++++++++++++++++
TPC
Prove a separação PSPACE =/= DEXT através da técnica da redução.
+++++++++++++++++++++++++++++++++++++++++++++++++++++
TPC
Mostre que:
(a) Se A se reduz a B, então A reduz-se a B;
(b) Se A é C-difícil e A se reduz a B, então B é também C-difícil;
(c) Se A é C-completo, A reduz-se a B e B está em C, então B é também C-completo;
(d) Se A é C-difícil, então A é co-C-difícil;
(e) Se C é fechado para a complementação, então se A é C-difícil, também A é C-difícil;
(f) As classes P, NP, co-NP, PSPACE estão fechadas para a redução.
+++++++++++++++++++++++++++++++++++++++++++++++++++++
TPC
Mostre que:
(a) A e B (não triviais) reduzem-se a A+B em tempo polinomial. Mostre que, se A e B (não triviais) se reduzem a C em tempo polinomial, então A+B reduz-se a C em tempo polinomial;
(b) P é o mais pequeno grau-m polinomial;
(c) Mostre que não há grau-m polinomial maximal.