EKSPACE

I kompleksitetsteori , EXPSPACE (Eksponentiel Space) står for den kompleksitet klassen af beslutningsproblemer der kan afgøres ved en deterministisk Turing-maskine i form af rum , hvor enhver polynomium er. Hvis man overvejer ikke-deterministiske Turing-maskiner, opnår man klassen NEXPSPACE . Ifølge Savitch's sætning er EXPSPACE = NEXPSPACE. ${\ displaystyle {\ mathcal {O}} \ left (2 ^ {p (n)} \ right)}$ ${\ displaystyle p (n)}$

Udtrykt i DSPACE / NSPACE- notationen gælder følgende:

${\ displaystyle {\ mbox {EXPSPACE}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {DSPACE}} \ left (2 ^ {n ^ {k}} \ right) = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {NSPACE}} \ venstre (2 ^ {n ^ {k}} \ højre).}$

Forholdet til andre kompleksitetsklasser

Følgende forhold er kendt:

NP PSPACE = NPSPACE EXPTIME NEXPTIME EXPSPACE = NEXPSPACE${\ displaystyle \ subseteq}$ ${\ displaystyle \ subseteq}$ ${\ displaystyle \ subseteq}$ ${\ displaystyle \ subseteq}$

og også PSPACE EXPSPACE ${\ displaystyle \ subset}$

fuldstændighed

Der er EXPSPACE-komplette problemer. Et eksempel er problemet med at bestemme, om to givne regulære udtryk producerer det samme sprog, hvor udtrykkene kun indeholder operatørforeningen , sammenkædning, Kleenisk kuvert og fordobling. I de sædvanlige notationer af regulære udtryk ville der kun være

• Forening :, genkende eller ,(x|y)xy
• Sammenkædning :, xygenkender xog derefter y,
• Kleenesche belægning :, x*genkender xså ofte som ønsket, muligvis slet ikke, og
• Fordobling :, x{2}registrerer xnøjagtigt to gange,

tilladt, hvor xog yallerede er under denne ordning, korrekt dannede udtryk eller bogstaver fra det givne alfabet. Tegnene (, |, ), *og {2}ses som ikke er en del af den bogstavelige alfabet. Kopieringen er blot endnu et symbol, mens sammenkædningen af xsig selv øger størrelsen på input betydeligt.

Det samme spørgsmål uden kløverskal repræsenterer et NEXPTIME-komplet problem.

litteratur

• Christos H. Papadimitriou : Computational Complexity . Addison-Wesley, Reading / Mass, 1995, ISBN 978-0-201-53082-7 , 20.1 And Beyond ... (engelsk). 

Weblinks

• EKSPACE . I: Complexity Zoo. (Engelsk)

Individuelle beviser

1. ↑ Meyer, AR og L. Stockmeyer . Ækvivalensproblemet for regulære udtryk med kvadrering kræver eksponentielt rum . 13. IEEE-symposium om skift og automatteori , oktober 1972, s. 125-129.