EXPTIM

În teoria complexității de calcul, clasa de complexitate EXPTIME (uneori numită EXP , din Exponential Time , „timp exponențial”), este ansamblul tuturor problemelor de decizie care pot fi rezolvate de o mașinărie Turing deterministă în timpul O (2 ^{p ( n )} ), unde p ( n ) este o funcție polinomială a lui n .

În ceea ce privește DTIME ,

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

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

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

Noi stim aia

P.

\subseteq

{\ displaystyle \ subseteq}

\ subseteq

NP

\subseteq

{\ displaystyle \ subseteq}

\ subseteq

PSPACE

\subseteq

{\ displaystyle \ subseteq}

\ subseteq

EXPTIM

\subseteq

{\ displaystyle \ subseteq}

\ subseteq

NEXPTIME

\subseteq

{\ displaystyle \ subseteq}

\ subseteq

EXPSPACE

și, de asemenea, prin teorema ierarhiei timpului și teorema ierarhiei spațiale , că

P.

\subsetneq

{\ displaystyle \ subsetneq}

\ subsetneq

EXPTIM Și NP

\subsetneq

{\ displaystyle \ subsetneq}

\ subsetneq

NEXPTIME Și PSPACE

\subsetneq

{\ displaystyle \ subsetneq}

\ subsetneq

EXPSPACE

deci cel puțin una dintre primele trei incluziuni și cel puțin una dintre ultimele trei incluziuni trebuie să fie corecte, dar nu se știe care sunt acestea, deși majoritatea experților consideră că toate incluziunile sunt corecte. Se știe, de asemenea, că dacă P = NP , atunci EXPTIME = NEXPTIME , clasa de probleme care pot fi rezolvate în timp exponențial de o mașină de Turing nedeterministă . ^[1] Mai precis, EXPTIME ≠ NEXPTIME dacă și numai dacă există limbi disparați în PN , care nu sunt în P. ^[2]

EXPTIME poate fi reformulat și ca clasă spațială APSPACE , probleme care pot fi rezolvate de o mașină alternativă Turing în spațiul polinomial. Acesta este un mod de a vedea acel PSPACE $\subseteq$ ${\ displaystyle \ subseteq}$ $\ subseteq$ EXPTIME, deoarece o mașină Turing alternativă este cel puțin la fel de puternică ca o mașină Turing deterministă. ^[3]

EXPTIME este o clasă într-o ierarhie exponențială de clase de complexitate cu limite de timp din ce în ce mai mari. Clasa 2-EXPTIME este definită similar cu EXPTIME, dar cu o limită de timp dublu exponențială $2^{2^{n}}$ ${\ displaystyle 2 ^ {2 ^ {n}}}$ ${\ displaystyle 2 ^ {2 ^ {n}}}$ . Acest lucru poate fi generalizat la limite de timp din ce în ce mai mari.

EXPTIME-complet

O problemă de decizie este EXPTIME-completă dacă este în EXPTIME și fiecare problemă din EXPTIME are o reducere de timp polinomială . Cu alte cuvinte, există un algoritm de timp polinomial care transformă cererile uneia dintre celelalte cereri cu același răspuns. Problemele care sunt EXPTIME-complete ar putea fi considerate ca fiind cele mai dificile probleme din EXPTIME. Rețineți că, deși nu știm dacă NP este sau nu un subset de P, știm că problemele EXPTIME-complete nu sunt în P; s-a dovedit, prin teorema ierarhiei timpului , că aceste probleme nu pot fi rezolvate în timp polinomial .

În teoria calculabilității , una dintre problemele de bază indecidabile este de a decide dacă se oprește o mașină Turing deterministă (MDT). Una dintre cele mai fundamentale probleme EXPTIME-complete este o versiune mai simplă a acesteia, care întreabă dacă un MDT se oprește cel mult în k pași. Dacă este în EXPTIME, deoarece o simulare trivială necesită timp O ( k ), iar intrarea k este codificată folosind bitul O (log k ). ^[4] Este EXPTIME-complet, deoarece, vorbind în bloc, îl putem folosi pentru a verifica dacă o mașină care rezolvă o problemă EXPTIME acceptă un număr exponențial de pași; nu va folosi mai mult. Aceeași problemă cu numărul de pași scrise în unar este P-complet .

Alte exemple de probleme complete EXPTIME includ problema generalizată a evaluării unei poziții în șah , ^[5] dame , ^[6] sau go (cu regulile japoneze ale ko) ^[7] . Aceste jocuri au probabilitatea de a fi EXPTIME-complete, deoarece jocurile pot dura pentru o serie de mișcări care sunt exponențiale la dimensiunea plăcii. În exemplul Go, regula japoneză a knockout-ului este suficient de intratabilă pentru a implica completitudinea EXPTIME, dar nu se știe dacă cele mai tratabile reguli americane sau chineze pentru joc sunt EXPTIME-complete.

În schimb, jocurile generalizate care pot dura pentru o serie de mișcări care sunt polinomiale la dimensiunea plăcii sunt adesea complete PSPACE . Același lucru este valabil și pentru jocurile exponențial lungi în care non-repetarea este automată.

Un alt set de probleme importante EXPTIME-complete se referă la circuite succinte . Circuitele slabe sunt mașini simple folosite pentru a descrie unele grafice într-un spațiu exponențial mai mic. Aceștia acceptă două numere de vârf ca intrare și ieșire dacă există o marjă între ele. Pentru multe probleme naturale ale graficului P-complet , unde graficul este exprimat într-o reprezentare naturală ca o matrice de adiacență , rezolvarea aceleiași probleme pe o reprezentare succintă a circuitului este EXPTIM-completă, deoarece intrarea este exponențial mai mică; dar acest lucru necesită dovezi netriviale, deoarece circuitele succinte pot descrie doar o subclasă de grafice. ^[8]

Notă

^ Christos Papadimitriou , Computational Complexity , Addison-Wesley, 1994, ISBN 0-201-53082-1 . secțiunea 20.1, p. 491.
^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. „Seturi rare în NP-P: EXPTIME versus NEXPTIME”. Informații și control , volumul 65, numerele 2/3, pp. 158–181. 1985. Despre Biblioteca digitală ACM
^ Papadimitriou (1994), secțiunea 20.1, corolar 3, p. 495.
^ Chris Umans, CS 21: Lecture 16 notes ( PDF ), pe cs.caltech.edu (arhivat din original la 8 iunie 2011) . Diapozitivul 21.
^ Aviezri Fraenkel și D. Lichtenstein, Calculul unei strategii perfecte pentru șah n × n necesită exponențial de timp în n , în J. Comb. Th. A , n. 31, 1981, pp. 199-214.
^ JM Robson, N by N checkers este Exptime complet , în SIAM Journal on Computing , vol. 13, n. 2, 1984, pp. 252-267, DOI : 10.1137 / 0213018 .
^ JM Robson, Complexitatea Go , în procesarea informațiilor; Proceedings of IFIP Congress , 1983, pp. 413-417.
^ Papadimitriou (1994), secțiunea 20.1, p. 492.

Portal IT

Portalul de matematică

[1] Christos Papadimitriou , Computational Complexity , Addison-Wesley, 1994, ISBN 0-201-53082-1 . secțiunea 20.1, p. 491.

[2] Juris Hartmanis, Neil Immerman, Vivian Sewelson. „Seturi rare în NP-P: EXPTIME versus NEXPTIME”. Informații și control , volumul 65, numerele 2/3, pp. 158–181. 1985. Despre Biblioteca digitală ACM

[3] Papadimitriou (1994), secțiunea 20.1, corolar 3, p. 495.

[4] Chris Umans, CS 21: Lecture 16 notes ( PDF ), pe cs.caltech.edu (arhivat din original la 8 iunie 2011) . Diapozitivul 21.

[Fraenkel1981-5] Aviezri Fraenkel și D. Lichtenstein, Calculul unei strategii perfecte pentru șah n × n necesită exponențial de timp în n , în J. Comb. Th. A , n. 31, 1981, pp. 199-214.

[robson1984-6] JM Robson, N by N checkers este Exptime complet , în SIAM Journal on Computing , vol. 13, n. 2, 1984, pp. 252-267, DOI : 10.1137 / 0213018 .

[7] JM Robson, Complexitatea Go , în procesarea informațiilor; Proceedings of IFIP Congress , 1983, pp. 413-417.

[8] Papadimitriou (1994), secțiunea 20.1, p. 492.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]