Undecidability Results for Low Complexity Time Classes

摘要

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 by Nies (1997, Bull. London Math. Soc.29, 683–692). The method can be applied, in fact, to all time classes given by a time constructible function which dominates all polynomials. By a similar method, we construct an oracle U such that Th(NPU, ⊆) is undecidable.