Automorphisms in the PTIME-Turing degrees of recursive sets (Q676317)

If \(A\) and \(B\) are sets then \(A\leq_T^p B\) if there is a polynomial time algorithm, with access to oracle \(B\), that can decide \(A\). Take the set of all recursive sets. If \(A\leq_T^p B\) and \(B\leq_T^p A\) then we will say \(A\) and \(B\) are equivalent. Let \({\mathbf R}\) be the resulting set of degrees, ordered by \(\leq_T^p\). The question arises as to whether this structure has any non-trivial automorphisms. This paper shows that this is a hard question. In this paper, the authors exhibit two oracles. Relative to one of them, there are no automorphisms. Relative to the other one, there are. Hence techniques that relativize will not suffice to answer the question. The construction of the oracles uses forcing.