Inverting the Turing jump in complexity theory

The paper investigates the invertibility of certain analogs of the Turing jump operator in the polynomial-time Turing degrees. If 𝒞 is some complexity class, the 𝒞-jump of a set A is the canonical 𝒞-complete set relative to A. It is shown that the PSPACE-jump and EXP-jump operators are not invertible, i.e., there is a PSPACE-hard (resp. EXP-hard) set that is not p-time Turing equivalent to the PSPACE-jump (resp. EXP-jump) of any set. It is also shown that if PH collapses to Σ_k^p, then the Σ_k ^p-jump is not invertible. In particular, if NP=co-NP, then the NP-jump is not invertible, witnessed, in particular, by G⊕SAT, where G is any 1-generic set. These results run contrary to the Friedberg (1957) Completeness Criterion in recursion theory, which says that every (recursive) Turing degree above 0´ is the Turing jump of another degree. The sets used in the paper to witness 𝒞-jump noninvertibility are all of the form G⊕C, cohere G is 1-generic and C is some 𝒞-complete set. Other facts regarding 1-generics G and G⊕SAT are also explored. In particular, G always lies in NP ^A-P^A for some A⩽G_tt^P, but if A⩽_⊕P-tt^p G_⊕SAT⩽_T^PSAT^A for some A, then G⩽_T^PA⊕SAT, which in turn implies either G⩽_T^P A or P≠NP