PROFILPELAJAR.COM

W obliczeniowej teorii złożoności klasa złożoności EXPTIME (czasami nazywana EXP lub DEXPTIME) jest zbiorem wszystkich problemów decyzyjnych, które mają wykładniczy czas wykonywania, tj. są rozwiązywalne przez deterministyczną maszynę Turinga w czasie O (2^p(n)), gdzie p(n) jest funkcją wielomianową n.

Definicja używająca DTIME:

{\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right)

Wiemy, że:

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE,

a także według twierdzenia o hierarchii czasu i twierdzenia o hierarchii przestrzeni, że

P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE,

więc co najmniej jedna z pierwszych trzech inkluzji i co najmniej jedna z trzech ostatnich inkluzji muszą być właściwe, ale nie wiadomo, które z nich są. Większość ekspertów uważa, że wszystkie inkluzje są prawidłowe. Wiadomo również, że jeśli P = NP, to EXPTIME = NEXPTIME, klasa problemów możliwych do rozwiązania w czasie wykładniczym przez niedeterministyczną maszynę Turinga^[1]. Dokładniej, EXPTIME ≠ NEXPTIME wtedy i tylko wtedy, gdy istnieją rzadkie języki w NP, które nie są w P^[2].

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 Turinga^[3].

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.

W teorii obliczeń jednym z podstawowych nierozstrzygalnych problemów jest problem stopu: decydowanie, czy deterministyczna maszyna Turinga rozwiązująca problem się zatrzyma. Jednym z najbardziej podstawowych problemów z EXPTIME-zupełnych jest jego prostsza wersja, która pyta, czy deterministyczna maszyna Turinga zatrzymuje się po co najwyżej k krokach. Odbywa się to w EXPTIME czasie, ponieważ trywialna symulacja wymaga czasu O(k), a wejście k jest kodowane za pomocą bitów O(log k), co powoduje wykładniczą liczbę symulacji. Jest on ukończony w trybie EXPTIME-zupełnym, ponieważ z grubsza możemy go użyć do ustalenia, czy maszyna rozwiązująca problem stopu akceptuje wykładniczą liczbę kroków; nie zużyje więcej przestrzeni^[4]. Ten sam problem z liczbą kroków zapisanych w systemie unarnym jest P-zupełny.

Inne przykłady problemów EXPTIME-zupełnych obejmują problem oceny pozycji w szachach^[5], warcabach^[6] lub Go (z japońskimi regułami ko). Te gry mają szansę na EXPTIME-zupełność, ponieważ mogą one trwać ilość ruchów, która jest wykładnicza w stosunku do wielkości planszy. W przykładzie Go japońska zasada ko jest na tyle trudna, aby sugerować EXPTIME-zupełność, ale nie wiadomo, czy bardziej przystępne amerykańskie lub chińskie reguły gry są EXPTIME-zupełne.

Natomiast gry, które mogą trwać przez wiele ruchów wielomianowych pod względem wielkości planszy, są często PSPACE-kompletne.

Przypisy

↑ Christos Papadimitriou: Computational Complexity. ISBN 0-201-53082-1.
↑ JurisJ. Hartmanis JurisJ., NeilN. Immerman NeilN., VivianV. Sewelson VivianV., Sparse Sets in NP−P: EXPTIME versus NEXPTIME, „Information and Control”, 65 (2/3), At ACM Digital Library, 1983, s. 382–391, DOI: 10.1145/800061.808769, ISBN 0-89791-099-0 .
↑ Papadimitriou (1994), section 20.1, corollary 3, page 495.
↑ Ding-ZhuD.Z. Du Ding-ZhuD.Z., Ker-IK.I. Ko Ker-IK.I., Theory of Computational Complexity, ISBN 978-1-118-59497-1 .
↑ Aviezri SA.S. Fraenkel Aviezri SA.S., DavidD. Lichtenstein DavidD., Computing a perfect strategy for n × n chess requires time exponential in n, „Journal of Combinatorial Theory, Series A”, 31 (2), 1981, s. 199–214, DOI: 10.1016/0097-3165(81)90016-9 .
↑ J.M.J.M. Robson J.M.J.M., N by N Checkers is Exptime Complete, „SIAM Journal on Computing”, 13 (2), s. 252–267, DOI: 10.1137/0213018 .