Sumários
Polynomial time hierarchy
19 dezembro 2023, 14:00 • José Félix Costa
Polynomial time hierarchy.
Polynomial time hierarchy using bounded quantification.
Collapse theorems.
Uniform diagonalization (part 2)
15 dezembro 2023, 13:30 • José Félix Costa
Uniform diagonalization and its applications (Ladner's theorem and other results).
Negative results for recursively presentability: NP - P, NP - NP-complete, P - FIN.
Uniform diagonalization (part 1)
12 dezembro 2023, 14:00 • 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.
Turing reduction in polynomial time
5 dezembro 2023, 14:00 • José Félix Costa
Turing reduction in polynomial time. Characterization.
Positive and negative relativizations.
Xu, Donner and Book' theorem. Separations P(A) =/=NP(A), DEXT(A) =/= NEXT(A).
Sets in NP(B), for some oracle B, that cannot be decided with a polynomial number of queries.