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.