Oracle Turing machines

24 novembro 2017, 10:00 • José Félix Costa

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

Some results on relative computation. Example theorem: If T is a tally set and DEXT(T) = DEXT, than T \in P.

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.