Undecidability results for low complexity degree structures
Rodney G. Downey, André Nies · 2002
We prove that the theory of EXPTIME degrees with respect to polynomial time Turing and many-one reducibility is undecidable. To do so we use a coding method based on ideal lattices of Boolean algebras which is introduced A. Nies. The method can be applied in fact to all hyper-polynomial time classes.