EXPTIME – Wikipedia, wolna encyklopedia

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:

${\displaystyle {\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].

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.