EXPTIME - EXPTIME
I beräkningskomplexitet teori , den komplexitetsklassen EXPTIME (ibland kallad EXP eller DEXPTIME är) uppsättningen av alla beslutsproblem som är lösbara genom en deterministisk Turing maskin i exponentiell tid , dvs i O (2 p ( n ) ) tid, där p ( n ) är en polynomfunktion av n .
EXPTIME är en intuitiv klass i en exponentiell hierarki av komplexitetsklasser med allt mer komplexa orakel eller kvantifieringsalternativ. Till exempel definieras klassen 2-EXPTIME på samma sätt som EXPTIME men med en dubbel exponentiell tidsgräns . Detta kan generaliseras till högre och högre tidsgränser.
EXPTIME kan också omformuleras som rymdklassen APSPACE, uppsättningen av alla problem som kan lösas av en alternerande Turing -maskin i polynomrum.
EXPTIME hänför sig till de andra grundläggande tid- och rymdkomplexitetsklasserna på följande sätt: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . Furthemore, vid tiden hierarkin sats och rymdhierarkin sats , är det känt att P ⊊ EXPTIME, NP ⊊ NEXPTIME och PSPACE ⊊ EXPSPACE.
Formell definition
När det gäller DTIME ,
Relationer till andra klasser
Det är känt att
och också, genom tid hierarki satsen och rymden hierarki sats , att
I uttrycken ovan betyder symbolen ⊆ "är en delmängd av", och symbolen ⊊ betyder "är en strikt delmängd av".
så minst en av de tre första inklusionerna och minst en av de tre sista inklusionerna måste vara korrekt, men det är inte känt vilka som är. De flesta experter tror att alla inkluderingar är korrekta. Det är också känt att om P = NP , då EXPTIME = NEXPTIME , klassen av problem som kan lösas under exponentiell tid av en icke -bestämd Turing -maskin . Närmare bestämt EXPTIME ≠ NEXPTIME om och endast om det finns glesa språk i NP som inte är i P .
EXPTIME kan omformuleras till rymdklassen APSPACE, uppsättningen av alla problem som kan lösas av en alternerande Turing -maskin i polynomrum. Detta är ett sätt att se PSPACE ⊆ EXPTIME, eftersom en alternerande Turing -maskin är minst lika kraftfull som en deterministisk Turing -maskin.
EXPTIME-komplett
Ett beslutsproblem är EXPTIME-komplett om det är i EXPTIME och varje problem i EXPTIME har en polynomtid på 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. Problem som är EXPTIME-kompletta kan ses som de svåraste problemen under EXPTIME. Lägg märke till att även om det är okänt om NP är lika med P, vet vi att EXPTIME-kompletta problem inte finns i P; det har bevisats att dessa problem inte kan lösas på polynomtid , med tidshierarkinsatsen .
Inom beräkningsteorin är ett av de grundläggande oavgörbara problemen stoppproblemet : att avgöra om en deterministisk Turing -maskin (DTM) stannar. Ett av de mest grundläggande EXPTIME-kompletta problemen är en enklare version av detta, som frågar om en DTM stannar i högst k steg. Det är i EXPTIME eftersom en trivial simulering kräver O ( k ) tid, och ingången k kodas med hjälp av O (log k ) bitar som orsakar ett exponentiellt antal simuleringar. Det är EXPTIME-komplett eftersom vi grovt sett kan använda det för att avgöra om en maskin som löser ett EXPTIME-problem accepterar i ett exponentiellt antal steg; det kommer inte att använda mer. Samma problem med antalet steg skrivna i unary är P-komplett .
Andra exempel på EXPTIME-kompletta problem inkluderar problemet med att utvärdera en position i generaliserat schack , dam eller Go (med japanska ko-regler). Dessa spel har en chans att bli EXPTIME-komplett eftersom spel kan pågå i ett antal drag som är exponentiellt i brädans storlek. I Go-exemplet är den japanska ko-regeln tillräckligt svårhanterlig för att kunna innebära EXPTIME-fullständighet, men det är inte känt om de mer handlingsbara amerikanska eller kinesiska reglerna för spelet är EXPTIME-kompletta.
Däremot är generaliserade spel som kan pågå för ett antal drag som är polynomiska i brädans storlek ofta PSPACE-kompletta . Detsamma gäller exponentiellt långa spel där icke-repetition sker automatiskt.
En annan uppsättning viktiga EXPTIME-kompletta problem avser kortfattade kretsar . Kortfattade kretsar är enkla maskiner som används för att beskriva några grafer i exponentiellt mindre utrymme. De accepterar två toppunktsnummer som input och output om det finns en kant mellan dem. För många naturliga P-kompletta grafproblem, där grafen uttrycks i en naturlig representation som en adjacensmatris , är lösningen av samma problem på en kortfattad kretsrepresentation EXPTIME-komplett, eftersom ingången är exponentiellt mindre; men detta kräver icke -bevis, eftersom kortfattade kretsar bara kan beskriva en underklass med grafer.
