2-EXPTIME
I beräkningskomplexitetsteori är komplexitetsklassen 2-EXPTIME (ibland kallad 2-EXP ) uppsättningen av alla beslutsproblem som kan lösas av en deterministisk Turing-maskin i O (2 2 p ( n ) ) tid, där p ( n ) är en polynomfunktion av n .
När det gäller DTIME ,
Vi vet
2-EXPTIME kan också omformuleras till rymdklassen AEXPSPACE, de problem som kan lösas av en alternerande Turingmaskin i exponentiellt rymden. Detta är ett sätt att se att EXPSPACE ⊆ 2-EXPTIME, eftersom en alternerande Turingmaskin är minst lika kraftfull som en deterministisk Turingmaskin.
2-EXPTIME är en klass i en hierarki av komplexitetsklasser med allt högre tidsgränser. Klassen 3-EXPTIME definieras på samma sätt som 2-EXPTIME men med en trefaldig exponentiell tidsgräns . Detta kan generaliseras till högre och högre tidsgränser.
Exempel
Exempel på algoritmer som kräver minst 2-EXPTIME inkluderar:
- Varje beslutsprocedur för Presburger-arithmetik kräver bevisligen minst dubbelt exponentiell tid
- Beräknar en Gröbner-bas över ett fält. I värsta fall kan en Gröbnerbas ha ett antal element som är dubbelt exponentiellt i antalet variabler. Å andra sidan är den värsta komplexiteten hos Gröbners basalgoritmer dubbelt exponentiell i antalet variabler såväl som i poststorleken.
- Att hitta en komplett uppsättning associativ-kommutativa förenare
- Tillfredsställande CTL + (som faktiskt är 2-EXPTIME-komplett)
- Kvantifierareliminering på verkliga slutna fält tar dubbelt exponentiell tid (se Cylindrisk algebraisk nedbrytning ) .
- Beräknar komplementet till ett reguljärt uttryck
2-EXPTIME-kompletta problem
Generaliseringar av många fullt observerbara spel är EXPTIME-kompletta. Dessa spel kan ses som speciella instanser av en klass av övergångssystem definierade i termer av en uppsättning tillståndsvariabler och åtgärder/händelser som ändrar värdena på tillståndsvariablerna, tillsammans med frågan om det finns en vinnande strategi . En generalisering av denna klass av helt observerbara problem till delvis observerbara problem lyfter komplexiteten från EXPTIME -komplett till 2-EXPTIME-komplett.
Se även
- ^ Christos Papadimitriou , Computational Complexity (1994), ISBN 978-0-201-53082-7 . Avsnitt 20.1, följd 3, sid 495.
- ^ Fischer, MJ och Michael O. Rabin , 1974, " " Super-Exponential Complexity of Presburger Arithmetic. Arkiverad 2006-09-15 på Wayback Machine " Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7 : 27–41
- ^ Dubé, Thomas W. (augusti 1990). "Strukturen av polynomideal och Gröbnerbaser". SIAM Journal on Computing . 19 (4): 750–773. doi : 10.1137/0219053 .
- ^ Kapur, Deepak; Narendran, Paliath (1992), "Dubbelexponentiell komplexitet för att beräkna en komplett uppsättning AC-unifiers", Proc. 7:e IEEE Symp. Logic in Computer Science (LICS 1992) , s. 11–21, doi : 10.1109/LICS.1992.185515 , ISBN 0-8186-2735-2 , S2CID 206437926 .
- ^ Johannsen, Jan; Lange, Martin (2003), "CTL + är komplett för dubbel exponentiell tid", i Baeten, Jos CM; Lenstra, Jan Karel ; Parrow, Joachim; Woeginger, Gerhard J. (red.), Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) ( PDF) , Lecture Notes in Computer Science, vol. 2719, Springer-Verlag, s. 767–775, doi : 10.1007/3-540-45061-0_60 , ISBN 978-3-540-40493-4 , arkiverad från originalet (PDF) den 20307-0 , retved 2030-09 2006-12-22 .
- ^ Gruber, Hermann; Holzer, Markus (2008). "Finite Automata, Digraph Connectivity, and Regular Expression Size" (PDF) . Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008) . Vol. 5126. s. 39–50. doi : 10.1007/978-3-540-70583-3_4 .
- ^ Jussi Rintanen (2004). "Komplexitet av planering med partiell observerbarhet" (PDF) . Proceedings of International Conference on Automated Planning and Scheduling . AAAI Press: 345–354.