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.