TESTE 2

18 dezembro 2020, 10:00 • José Félix Costa

Realização do segundo de dois testes relativos a avaliação contínua.

NP-completeness

16 dezembro 2020, 16:30 • José Félix Costa

Boolean formulas. Quantified Boolean formulas.

NP-completeness of SAT, CNF-SAT.

PSPACE-completeness of QBF.

NP-completeness of CLIQUE.

Polynomial time hierarchy

11 dezembro 2020, 10:00 • José Félix Costa

The polynomial time hierarchy. 

Polynomial time hierarchy by means of bounded quantification. Alternation.

Collapse theorems.

Uniform diagonalization

9 dezembro 2020, 16:30 • José Félix Costa

Recursively presentable computational classes. 

P(A) for a decidable A, P, PSPACE, NP, NP-complete, co-NP, co-NP-complete, and PSPACE-complete.

Uniform diagonalization and its applications (Ladner's theorem and other results). 

Negative results for recursively presentability: NP - P, NP - NP-complete, P - FIN. 

Turing reduction in polynomial time

4 dezembro 2020, 10:00 • José Félix Costa

Conclusão do assunto da aula anterior.