Uniform diagonalization

5 dezembro 2018, 16: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.

Uniform diagonalization and its applications (Ladner's theorem and other results). Negative results for recursively presentability: NP - P, NP - NP-complete, P - FIN. 

Relativisation

30 novembro 2018, 10:00 • José Félix Costa

Proof of Xu, Donner and Book' theorem.

NP-completeness of CNF-SAT and VERTEX-COVER.

Oracle Turing machines

28 novembro 2018, 16:00 • José Félix Costa

Turing reduction in polynomial time. Characterization. Example: MAXCLIQUE <= CLIQUE.

Equivalence between closure under complementation and closure under Turing reduction for some complexity classes, such like NP and co-NP.

The open problem NP =/= co-NP.

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.

NP-completeness and PSPACE-completeness

23 novembro 2018, 10:00 • José Félix Costa

Boolean formulas. Quantified Boolean formulas.

NP-completeness of SAT and CLIQUE.

PSPACE-completeness of QBF.

NP- and PSPACE-complete sets

21 novembro 2018, 16:00 • José Félix Costa

Many to one reduction in polynomial time. Hard and complete sets.

Proof of the separation PSPACE =/= DEXT through a m-reduction argument.

NP-completeness of K.

Context sensitive grammars. That the class of sets generable by context sensitive grammars is NSPACE(n).

PSPACE-completeness of CSG-ACC.