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 (2p(n)), gdzie p(n) jest funkcją wielomianową n.

Definicja używająca DTIME:

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

  1. ↑ Christos Papadimitriou: Computational Complexity. ISBN 0-201-53082-1.
  2. ↑ Juris Hartmanis, Neil Immerman, Vivian Sewelson, 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.
  3. ↑ Papadimitriou (1994), section 20.1, corollary 3, page 495.
  4. ↑ Ding-Zhu Du, Ker-I Ko, Theory of Computational Complexity, ISBN 978-1-118-59497-1.
  5. ↑ Aviezri S Fraenkel, David Lichtenstein, 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.
  6. ↑ J.M. Robson, N by N Checkers is Exptime Complete, „SIAM Journal on Computing”, 13 (2), s. 252–267, DOI: 10.1137/0213018.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.