WYJĄTKOWO

W teorii złożoności , EXPTIME (lub EXP ) to klasa złożoności , która jest zbiorem problemów decyzyjnych zdecydowały przez deterministycznej maszyny Turinga w wykładniczym czasie .

Definicja formalna

Jeśli nazwiemy zbiór wszystkich problemów, które mogą być rozwiązane przez deterministyczne maszyny Turinga przy użyciu czasu dla funkcji o rozmiarze danych wejściowych , to możemy formalnie zdefiniować EXPTIME przez: ${\ mbox {DTIME}} (t (n))$ $O (t (n))$ $t$ $nie$

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

Nieruchomości

Jak pokazano na obrazku po prawej, mamy następujące inkluzje: P NP PSPACE EXPTIME. $\ scriptstyle \ subseteq$ $\ scriptstyle \ subseteq$ $\ scriptstyle \ subseteq$

EXPTIME to stosunkowo duża klasa, która zawiera problemy uważane za niemożliwe do skutecznego rozwiązania. Ale są większe klasy, takie jak EXPSPACE i NEXPTIME (odpowiednio problemy, które można rozwiązać w przestrzeni wykładniczej iw czasie wykładniczym na maszynie niedeterministycznej ).

Za pomocą argumentu „ padding ” otrzymujemy następujące twierdzenie związane z problemem P = NP :

Twierdzenie - jeśli EXPTIME NEXPTIME to P NP $\ scriptstyle \ neq$ $\ scriptstyle \ neq$

Ponadto, zgodnie z deterministycznym twierdzeniem o hierarchii czasu , klasa P różni się od klasy EXPTIME.

Klasa EXPTIME jest równa klasie APSPACE, odpowiedniku PSPACE na naprzemiennej maszynie Turinga , zgodnie z twierdzeniem Chandry - Kozen - Stockmeyera .

W złożoności opisowej EXPTIME odpowiada SO (LFP), tj. Logice drugiego rzędu z najmniejszym punktem stałym.

WYJĄTKOWE problemy

Problem zatrzymania maszyny Turinga po k kroku czasowym (gdzie k jest zapisane w notacji binarnej) jest EXPTIME- zakończony . Jest to ograniczenie problemu zatrzymania , który w ogólnym przypadku jest nierozstrzygalny .

Problem spełnialności następujących logik jest WYJĄTKOWY-kompletny:

logika czasowa CTL jest EXPTIME-Complete ;
dynamiczna logika zdań (PDL).

Krótkie wersje niektórych problemów P-pełnych są zakończone EXPTIME, np. SUCCINCT CIRCUIT VALUE .

EXPTIME i gry dla dwóch graczy

Poprzez naprzemienne maszyny Turinga i przez równość między klasą APSPACE (w przestrzeni wielomianowej na maszynie naprzemiennej) a EXPTIME, Chandra i Stockmeyer zaprezentowali dwuosobowe gry logiczne z doskonałymi informacjami i grami na wykresach, które są EXPTIME-kompletne.

Jedna z gier logicznych, EXPTIME-complete, jest przedstawiana jako gra dla dwóch graczy o nazwie PEEK. Jedno pudełko jest dziurkowane i zawiera płyty perforowane gracza 1 i płyty perforowane gracza 2 . Gracze grają po kolei: albo nic nie robi, albo ciągnie lub popycha jeden ze swoich talerzy. Jeden z graczy wygrywa, jeśli uda mu się ustawić pionowo serię otworów w całym pudełku. Jednym z przykładów PEEK jest opis dwóch zestawów perforowanych (dowolnie dużych) płyt. Bardziej formalnie, gra PEEK, nazwana G4 w artykule Chandry i Stockmeyera, wygląda następująco. Jako dane wejściowe podajemy sobie formułę logiczną w rozłącznej postaci normalnej z maksymalnie 13 literałami na klauzulę. Dajemy sobie również wstępną wycenę na 2k zmiennych pojawiających się we wzorze. Zbiór zmiennych jest podzielony na dwie części: k zmiennych kontrolowanych przez pierwszego gracza i k zmiennych kontrolowanych przez drugiego. Pierwszy gracz, który sprawi, że formuła będzie prawdziwa, wygrywa. Problem decyzyjny polega na podjęciu decyzji, czy pierwszy gracz ma zwycięską strategię.

Praca Chandry Stockmeyera umożliwiła następnie wykazanie, że uogólnione wersje gier, takie jak szachy , warcaby i go, są WYJĄTKOWO kompletne; te gry zostały uogólnione w tym sensie, że rozmiar planszy jest podawany jako dane wejściowe do problemu. Ponadto logika z ograniczeniami jest narzędziem do zademonstrowania WYJĄTKOWEJ twardości niektórych gier.

Ponadto praca Chandry i Stockmeyera pozwoliła Littmanowi wykazać, że problem automatycznego planowania, w którym działania są niedeterministyczne, a agent ma doskonałe informacje, jest WYJĄTKOWYM trudnym zadaniem.

Uwagi i odniesienia

(w) Sanjeev Arora i Boaz Barak , Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , rozdz. 2.6.2 („EXP i NEXP”).
.
(w) Klasa EXPTIME w Zoo Complexity .
(w) Chris Umans, „ CS21 Decidability and tractability (Reading 16-17) ” [PDF] , Caltech ,2017.
(w) „ Prawie optymalna metoda wnioskowania o działaniach ” , Journal of Computer and System Sciences , t. 20 N O 21 st kwiecień 1980, s. 231–254 ( ISSN 0022-0000 , DOI 10.1016 / 0022-0000 (80) 90061-6 , czytaj online , dostęp: 5 marca 2018 ).
.
(w) Aviezri Fraenkel i D. Lichtenstein, „ Obliczanie doskonałej strategii dla szachów n × n wymaga wykładniczego czasu w n ” , J. Comb. P a. , N O 31,Dziewiętnaście osiemdziesiąt jeden, s. 199-214.
(en) JM Robson, „ N by N checkers is full EXPTIME ” , SIAM Journal we Computing , vol. 13 N O 21984, s. 252-267 ( DOI 10.1137 / 0213018 ).
(en) JM Robson, „The complexity of Go” , w: Przetwarzanie informacji; Obrady Kongresu IFIP ,1983, s. 413-417.
(w) Robert Aubrey Hearn , Games, Puzzles and computation (PhD)1 st styczeń 2006( czytaj online ).
Michael L. Littman , „ Probabilistic Propositional Planning: Representations and Complexity ”, In Proceedings of the 14th National Conference on Artificial Intelligence , MIT Press,1997, s. 748–754 ( czyt. Online , przeglądano 10 lutego 2019 r. )

Zobacz też

Powiązane artykuły

Teoria złożoności (informatyka teoretyczna)
Klasa złożoności
E (złożoność) : klasa problemów EXPTIME, które mają wykładnik liniowy jako funkcję rozmiaru, innymi słowy E = DTIME . ${\ Displaystyle (2 ^ {O (n)})}$

Linki zewnętrzne

(en) Klasa EXPTIME w Zoo Complexity