AUTOMORPHISMS IN THE PTIME-TURING DEGREES OF RECURSIVE SETS

We consider questions related to the rigidity of the structure R, the PTIME-Turing degrees of recursive sets of strings together with PTIME- Turing reducibility, less than or equal to(pT), and related structures ; do these structures have nontrivial automorphisms? We prove that the re is a nontrivial automorphism of an ideal of R. This can be rephrase d in terms of partial relativizations. We consider the sets which are PTIME-Turing computable from a set A, and call this class PTIME(A). Ou r result can be stated as follows: There is an oracle, A, relative to which the PTIME-Turing degrees are not rigid (i.e. there is a nontrivi al automorphism of the structure [PTIME(A), less than or equal to(pT)] ). Furthermore, the automorphism can be made to preserve the complexit y classes DTIME(A)(n(k)) (the collection of sets computable from A by a deterministic computation with time bound of order n(k)) for all k g reater than or equal to 1, or to move any DTIME(A)(n(k)) for n greater than or equal to 2. From the existence of such an automorphism we con clude as a corollary that there is an oracle A relative to which the c lasses DTIME(n(k)) are not definable over R. We carry out the correspo nding partial relativization for the many-one degrees to construct an oracle, A, relative to which the PTIME-many-one degrees relative to A have a nontrivial automorphism, and one relative to which the lattice of sets in PTIME(A) under inclusion have a nontrivial automorphism. Th e proof is phrased as a forcing argument; we construct the set A to me et a particular collection of dense sets in our notion of forcing. Rou ghly, the dense sets will guarantee that if A meets these sets and we split A into two pieces, A(0) and A(1), in a simple way, and then swit ching the roles of A(0) and A(1) in all computations from A will produ ce an automorphism of the ideal of PTIME-degrees below A. We force A(0 ) and A(1) to have different PTIME-Turing degree; this will then make the automorphism nontrivial. An appropriately generic set A is constru cted using a priority argument.