EXPONERING - EXPSPACE
I beräkningskomplexitet teori , EXPSPACE är uppsättningen av alla beslutsproblem lösbara genom en deterministisk Turing maskin i exponentiell utrymme , det vill säga i rymden, där är ett polynom funktion av . Vissa författare begränsar sig till att vara en linjär funktion , men de flesta författare kallar istället den resulterande klassen ESPACE . Om vi istället använder en icke -bestämd maskin får vi klassen NEXPSPACE , som är lika med EXPSPACE av Savitch's sats .
Ett beslutsproblem är EXPSPACE-komplett om det är i EXPSPACE , och varje problem i EXPSPACE har en polynomtid-många-en-minskning . Med andra ord finns det ett polynom tid algoritm som omvandlar förekomster av ett till exempel på den andra med samma svar. EXPSPACE-kompletta problem kan ses som de svåraste problemen i EXPSPACE .
EXPSPACE är en strikt superset av PSPACE , NP och P och antas vara en strikt superset av EXPTIME .
Formell definition
När det gäller DSPACE och NSPACE ,
Exempel på problem
Ett exempel på ett EXPSPACE-komplett problem är problemet med att erkänna om två reguljära uttryck representerar olika språk, där uttrycken är begränsade till fyra operatörer: union, sammanfogning , Kleene-stjärnan (noll eller fler kopior av ett uttryck) och kvadrering ( två kopior av ett uttryck).
Om Kleene-stjärnan utelämnas, blir det problemet NEXPTIME -complete , vilket är som EXPTIME-complete , förutom att det är definierat i termer av icke-deterministiska Turing-maskiner snarare än deterministiska.
Det har också visats av L. Berman 1980 att problemet med att verifiera/förfalska alla första ordens uttalanden om reella tal som endast innefattar addition och jämförelse (men ingen multiplikation ) är i EXPSPACE .
Alur och Henzinger utökade Linjär temporal logik med tider (heltal) och bevisar att validitetsproblemet för deras logik är EXPSPACE-komplett.
Täckbarhetsproblemet för Petri Nets är EXPSPACE -komplett. Problemet med nåbarhet för Petri -nät var känt för att vara EXPSPACE -hårt länge, men visade sig vara icke -elementärt, så det är bevisligen inte i EXPSPACE .
Förhållande till andra klasser
EXPSPACE är känd att vara en strikt superset av PSPACE , NP , och P . Det misstänks vidare vara en strikt superset av EXPTIME , men detta är inte känt.
Se även
Referenser
- ^ Meyer, AR och L. Stockmeyer . Ekvivalensproblemet för reguljära uttryck med kvadrering kräver exponentiellt utrymme . 13: e IEEE -symposiet om växling och automatteori , oktober 1972, s. 125–129.
- ^ Alur, Rajeev; Henzinger, Thomas A. (1994-01-01). "En riktigt temporär logik". J. ACM . 41 (1): 181–203. doi : 10.1145/174644.174651 . ISSN 0004-5411 .
- ^ Lipton, R. (1976). "Problemet med nåbarhet kräver exponentiellt utrymme" . Teknisk rapport 62 . Yale universitet.
- ^ Charles Rackoff (1978). "Täcknings- och begränsningsproblem för vektortilläggssystem". Teoretisk datavetenskap : 223-231.
- ^ Lipton, R. (1976). "Problemet med nåbarhet kräver exponentiellt utrymme" . Teknisk rapport 62 . Yale universitet.
- ^ Wojciech Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki (2019). "Problemet med nåbarhet för Petri -nät är inte elementärt". STOCK 19 .
- Berman, Leonard (1 maj 1980). "Komplexiteten i logiska teorier" . Teoretisk datavetenskap . 11 (1): 71–77. doi : 10.1016/0304-3975 (80) 90037-7 .
- Michael Sipser (1997). Introduktion till beräkningsteorin . PWS Publishing. ISBN 0-534-94728-X.Avsnitt 9.1.1: Exponentiell rymdkomplett, s. 313–317. Demonstrerar att bestämning av ekvivalens för reguljära uttryck med exponentiering är EXPSPACE-komplett.
