2-EXPTIME

계산 복잡도 이론에서 2-EXPTIME(때로는 2-EXP라고도 하며, 2EXPTIME으로 쓰기도 함)은 결정 문제들의 집합으로, p(n)이 n의 다항 함수일 때 결정 튜링 기계가 O(22p(n))시간 내에 풀 수 있는 문제들의 집합이다.

DTIME의 관점에서 보면 다음과 같다.

𝟤-𝖤𝖷𝖯𝖳𝖨𝖬𝖤=⋃k∈ℕ𝖣𝖳𝖨𝖬𝖤(22nk).

다른 복잡도 종류와의 비교

다음과 같은 관계가 알려져 있다.

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARY.

2-EXPTIME은 교대 튜링 기계가 지수 공간에서 풀 수 있는 문제들의 집합인 공간 종류 AEXPSPACE로 재정의할 수 있다. 이는 교대 튜링 기계가 결정 튜링 기계보다 최소한 같거나 더 강력하기 때문에 EXPSPACE ⊆ 2-EXPTIME임을 알 수 있는 하나의 방법이다.

2-EXPTIME은 시간 경계가 점차 높아지는 복잡도 종류 계층 중 하나이다. 3-EXPTIME은 2-EXPTIME과 유사하게 정의되지만 3중 지수 시간 경계인 222nk를 가진다. 이는 더 높은 시간 경계로 일반화할 수 있다.

예시

최소한 2중 지수 시간이 필요한 알고리즘의 예는 다음과 같다.

2-EXPTIME-완전 문제

논리

CTL+(계산 트리 논리)의 만족 가능성 문제는 2-EXPTIME-완전이다. ATL*(교대 시간 논리)의 만족 가능성 문제는 2-EXPTIME-완전이다.

함축적 관련 논리(Implicational Relevance Logic)는 2-EXPTIME-완전이다.

교집합을 포함한 명제 동적 논리(IPDL)의 만족 가능성 문제는 2-EXPTIME-완전이다.

계획

완전 관측 가능한 많은 게임들의 일반화는 EXPTIME-완전이다. 이러한 게임들은 상태 변수들의 집합과 상태 변수의 값을 변경하는 동작/이벤트, 그리고 승리 전략이 존재하는지에 대한 질문으로 정의된 전이 시스템 종류의 특정 사례로 볼 수 있다. 이러한 완전 관측 가능한 문제 종류를 부분 관측 가능한 문제로 일반화하면 복잡도가 EXPTIME-완전에서 2-EXPTIME-완전으로 상승한다.

합성

LTL(선형 시간 논리) 합성(LTL 명세를 만족하는 반응형 모듈이 존재하는지 결정하는 문제)은 2-EXPTIME-완전이다.

같이 보기

각주

  1. ↑ 크리스토스 파파디미트리우, Computational Complexity (1994), ISBN 978-0-201-53082-7. 20.1절, 따름정리 3, 495쪽.
  2. ↑ Fischer, M. J., and Rabin, M. O., 1974, ""Super-Exponential Complexity of Presburger Arithmetic. 보관됨 2006-09-15 - 웨이백 머신" Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41
  3. ↑ Dubé, Thomas W. (August 1990). “The Structure of Polynomial Ideals and Gröbner Bases”. 《SIAM Journal on Computing》 19 (4): 750–773. doi:10.1137/0219053.
  4. ↑ Kapur, Deepak; Narendran, Paliath (1992), 〈Double-exponential complexity of computing a complete set of AC-unifiers〉, 《[1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science》, 11–21쪽, doi:10.1109/LICS.1992.185515, ISBN 0-8186-2735-2, S2CID 206437926.
  5. ↑ Ben-Or, Michael; Kozen, Dexter; Reif, John (1986년 4월 1일). “The complexity of elementary algebra and geometry”. 《Journal of Computer and System Sciences》 32 (2): 251–264. doi:10.1016/0022-0000(86)90029-2. ISSN 0022-0000.
  6. ↑ Gruber, Hermann; Holzer, Markus (2008). 〈Finite Automata, Digraph Connectivity, and Regular Expression Size〉. 《Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008)》. 39–50쪽. doi:10.1007/978-3-540-70583-3_4.
  7. ↑ Johannsen, Jan; Lange, Martin (2003), 〈CTL+ is complete for double exponential time〉, Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim; Woeginger, Gerhard J. (편집), 《Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003)》 (PDF), Lecture Notes in Computer Science 2719, Springer-Verlag, 767–775쪽, doi:10.1007/3-540-45061-0_60, ISBN 978-3-540-40493-4, 2007년 9월 30일에 원본 문서 (PDF)에서 보존된 문서, 2006년 12월 22일에 확인함.
  8. ↑ Schewe, Sven (2008). 〈ATL* Satisfiability is 2EXPTIME-Complete〉 (영어). Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (편집). 《Automata, Languages and Programming》. Lecture Notes in Computer Science 5126. Berlin, Heidelberg: Springer. 373–385쪽. doi:10.1007/978-3-540-70583-3_31. ISBN 978-3-540-70583-3.
  9. ↑ Schmitz, Sylvain (2016). “Implicational Relevance Logic Is 2-Exptime-Complete”. 《The Journal of Symbolic Logic》 81 (2): 641–661. arXiv:1402.0705. doi:10.1017/jsl.2015.7. ISSN 0022-4812. JSTOR 43864316.
  10. ↑ Lange, Martin; Lutz, Carsten (2005). “2-Exptime Lower Bounds for Propositional Dynamic Logics with Intersection”. 《The Journal of Symbolic Logic》 70 (4): 1072–1086. doi:10.2178/jsl/1129642115. ISSN 0022-4812. JSTOR 27588414.
  11. ↑ Jussi Rintanen (2004). “Complexity of Planning with Partial Observability” (PDF). 《Proceedings of International Conference on Automated Planning and Scheduling》 (AAAI Press): 345–354.
  12. ↑ Pnueli, A.; Rosner, R. (1989년 1월 3일). 〈On the synthesis of a reactive module〉. 《Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89》. New York, NY, USA: Association for Computing Machinery. 179–190쪽. doi:10.1145/75277.75293. ISBN 978-0-89791-294-5.