EXPTIME
W teorii złożoności obliczeniowej klasa złożoności EXPTIME (czasami nazywana EXP lub DEXPTIME ) jest zbiorem wszystkich problemów decyzyjnych , które są rozwiązywane przez deterministyczną maszynę Turinga w czasie wykładniczym , tj. w czasie O (2 p ( n ) ), gdzie p ( n ) jest funkcją wielomianową n .
EXPTIME to jedna intuicyjna klasa w wykładniczej hierarchii klas złożoności z coraz bardziej złożonymi wyroczniami lub zmianami kwantyfikatorów. Na przykład klasa 2-EXPTIME jest zdefiniowana podobnie do EXPTIME, ale z podwójnie wykładniczym ograniczeniem czasowym. Można to uogólnić na coraz wyższe granice czasowe.
EXPTIME można również przeformułować jako klasę przestrzeni APSPACE, zbiór wszystkich problemów, które można rozwiązać za pomocą naprzemiennej maszyny Turinga w przestrzeni wielomianowej.
EXPTIME odnosi się do innych podstawowych klas złożoności czasu i przestrzeni w następujący sposób: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . Ponadto z twierdzenia o hierarchii czasu i twierdzenia o hierarchii przestrzeni wiadomo, że P ⊊ EXPTIME, NP ⊊ NEXPTIME i PSPACE ⊊ EXPSPACE.
Definicja formalna
Pod względem DTIME ,
Relacje z innymi klasami
Wiadomo, że
a także, przez twierdzenie o hierarchii czasu i twierdzenie o hierarchii przestrzeni , że
W powyższych wyrażeniach symbol ⊆ oznacza „jest podzbiorem”, a symbol ⊊ oznacza „jest ścisłym podzbiorem”.
więc co najmniej jedna z pierwszych trzech inkluzji i co najmniej jedna z trzech ostatnich inkluzji musi być właściwa, ale nie wiadomo, które z nich są. Większość ekspertów [ kto? ] uważa, że wszystkie inkluzje są prawidłowe. Wiadomo również, że jeśli P = NP , to EXPTIME = NEXPTIME , klasa problemów, które można rozwiązać w czasie wykładniczym przez niedeterministyczną maszynę Turinga . Dokładniej EXPTIME ≠ NEXPTIME wtedy i tylko wtedy, gdy w NP istnieją rzadkie języki , których nie ma w P .
EXPTIME można przeformułować jako klasę przestrzeni APSPACE, zbiór wszystkich problemów, które można rozwiązać za pomocą naprzemiennej maszyny Turinga w przestrzeni wielomianowej. Jest to jeden ze sposobów sprawdzenia, czy PSPACE ⊆ EXPTIME, ponieważ naprzemienna maszyna Turinga jest co najmniej tak potężna jak deterministyczna maszyna Turinga.
EXPTIME-ukończono
Problem decyzyjny jest EXPTIME-zupełny, jeśli jest w EXPTIME, a każdy problem w EXPTIME ma wielomianową redukcję do wielu jeden. Innymi słowy, istnieje algorytm czasu wielomianowego , który przekształca instancje jednego na instancje drugiego z tą samą odpowiedzią. Problemy, które są EXPTIME-kompletne, można uważać za najtrudniejsze problemy w EXPTIME. Zauważ, że chociaż nie wiadomo, czy NP jest równe P, wiemy, że problemy EXPTIME-zupełne nie należą do P; udowodniono, że problemów tych nie można rozwiązać w czasie wielomianowym , twierdzeniem o hierarchii czasu .
W teorii obliczalności jednym z podstawowych nierozstrzygalnych problemów jest problem zatrzymania : decyzja, czy deterministyczna maszyna Turinga (DTM) się zatrzymuje. Jednym z najbardziej fundamentalnych problemów EXPTIME-complete jest prostsza wersja tego, która pyta, czy DTM zatrzymuje się w co najwyżej k krokach. Jest w EXPTIME, ponieważ trywialna symulacja wymaga czasu O( k ), a wejście k jest kodowane przy użyciu bitów O (log k ), co powoduje wykładniczą liczbę symulacji. Jest EXPTIME-zupełny, ponieważ, mówiąc z grubsza, możemy go użyć do określenia, czy maszyna rozwiązująca problem EXPTIME akceptuje w wykładniczej liczbie kroków; więcej nie użyje. Ten sam problem z liczbą kroków zapisanych w systemie jednoargumentowym to P-complete .
Inne przykłady problemów EXPTIME-zupełnych obejmują problem oceny pozycji w uogólnionych szachach , warcabach lub Go (z japońskimi zasadami ko). Te gry mają szansę zakończyć się EXPTIME, ponieważ gry mogą trwać przez wiele ruchów, które są wykładnicze w rozmiarze planszy. W przykładzie Go japońska reguła ko jest wystarczająco trudna, aby sugerować EXPTIME-zupełność, ale nie wiadomo, czy bardziej podatne na stosowanie amerykańskie lub chińskie zasady gry są EXPTIME-zupełne.
Natomiast uogólnione gry, które mogą trwać przez wiele ruchów, które są wielomianowe w rozmiarze planszy, są często PSPACE-complete . To samo dotyczy wykładniczo długich gier, w których brak powtórzeń jest automatyczny.
Inny zestaw ważnych problemów EXPTIME-complete dotyczy zwięzłych obwodów. Zwięzłe obwody to proste maszyny używane do opisywania niektórych wykresów w wykładniczo mniejszej przestrzeni. Akceptują dwie liczby wierzchołków jako dane wejściowe i wyjściowe, niezależnie od tego, czy istnieje między nimi krawędź. W przypadku wielu naturalnych P-zupełnymi , gdzie wykres jest wyrażony w naturalnej reprezentacji, takiej jak macierz sąsiedztwa , rozwiązanie tego samego problemu na zwięzłej reprezentacji obwodu jest EXPTIME-zupełne, ponieważ wejście jest wykładniczo mniejsze; ale wymaga to nietrywialnego dowodu, ponieważ zwięzłe obwody mogą opisywać tylko podklasę grafów.