Abstract:
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 was introduced in [7]. The method can be applied in fact
to all hyper-polynomial time classes.