EXPTIME można również przeformułować jako klasę przestrzeni APSPACE, problemy, które można rozwiązać za pomocą naprzemiennej maszyny Turinga w przestrzeni wielomianowej. Jest to jeden ze sposobów, aby zobaczyć PSPACE ⊆ EXPTIME, ponieważ naprzemienna maszyna Turinga jest co najmniej tak potężna jak deterministyczna maszyna TuringaPapadimitriou (1994), section 20.1, corollary 3, page 495..
EXPTIME-zupełność Problem decyzyjny jest EXPTIME-zupełny, jeśli występuje w EXPTIME, a każdy problem w EXPTIME ma wielorakie zmniejszenie wielokrotności. Innymi słowy, istnieje algorytm o złożoności czasu wielomianowego, który przekształca wystąpienia jednego w wystąpienie drugiego o tej samej odpowiedzi. Problemy EXPTIME-zupełne można uznać za „najtrudniejsze” w klasie EXPTIME. Chociaż nie wiadomo, czy NP jest równe P, wiemy, że problemy EXPTIME-zupełne nie występują w P; udowodniono, że te problemy nie mogą być rozwiązane w czasie wielomianowym przez twierdzenie o hierarchii czasu.