2회차

2-EXPTIME

계산 복잡도 이론에서, 복잡도 클래스 2-EXPTIME(때로는 2-EXP라고도 함)은 결정론적 튜링 기계가 O(22p(n)) 시간에 풀 수 있는 모든 결정 문제의 집합이다. 여기서 p(n)는 n의 다항식 함수이다.

DTIME의 관점에서 보면

우리는 알고 있다.

P np NP 、 PSPACE 、 EXPTIME 、 NEXPTIME 、 EXPTIME 、 2-EXPTIME 、 ELEMARY 。

2-EXPTIME은 또한 공간 클래스 AEXPACE로 재구성될 수 있으며, 이는 지수 공간에서 교대 튜링 기계에 의해 해결될 수 있는 문제이다.교대 튜링 기계는 적어도 결정론적 튜링 [1]기계만큼 강력하기 때문에 이것은 EXPSPACE 2 2-EXPTIME을 볼 수 있는 하나의 방법이다.

2-EXPTIME은 복잡도 클래스의 계층에 포함되는1개의 클래스이며, 시간범위는 점점 높아집니다.클래스 3-EXPTIME은 2-EXPTIME과 유사하게 정의되지만, 3배의 지수 시간 이 2 2입니다.이는 점점 더 높은 시간 범위로 일반화할 수 있습니다.

예

2개 이상의 EXPTIME이 필요한 알고리즘의 예는 다음과 같습니다.

  • Presburger 산술에 대한 각 결정 절차는 입증할 수 있도록 최소 두 배의 지수 시간을 필요로 한다.
  • 필드에 대한 Gröbner 기반 계산.최악의 경우, 그뢰브너 베이스는 변수 수가 두 배로 기하급수적인 다수의 요소를 가질 수 있다.한편, 그로브너 기반 알고리즘의 최악의 경우 복잡성은 입력 [3]크기뿐만 아니라 변수의 수에서도 두 배로 기하급수적이다.
  • 전체 연관-가환 통일어 집합 찾기
  • CTL+ 만족(실제로 2-EXPTIME-완전)
  • 실제 닫힌 필드에서의 양자화 소거에는 두 배의 지수 시간이 소요됩니다(원통형 대수 분해 참조).
  • 정규식의[6] 보완 계산

2 EXPTIME 완전 문제

완전히 관찰할 수 있는 많은 게임의 일반화는 EXPTIME-complete이다.이러한 게임은 승리 전략이 존재하는지 여부에 대한 질문과 함께 상태 변수와 상태 변수의 값을 변경하는 행동/이벤트 집합의 관점에서 정의된 전환 시스템 클래스의 특정 인스턴스로 볼 수 있습니다.완전히 관찰 가능한 문제의 이 클래스를 부분적으로 관찰 가능한 문제로 일반화하면 복잡성이 EXPTIME-complete에서 2-EXPTIME-complete로 [7]높아진다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Christos Papadimitriou, 계산 복잡도(1994), ISBN978-0-201-53082-7.섹션 20.1, 결론 3, 495페이지.
  2. ^ 피셔, M. J.와 마이클 O. 라빈, 1974년 "프레즈버거 산수의 초지수 복소수.2006년 9월 15일 응용수학 SIAM-AMS 심포지엄 'Wayback Machine'에서의 아카이브 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", Proc. 7th IEEE Symp. Logic in Computer Science (LICS 1992), pp. 11–21, doi:10.1109/LICS.1992.185515, ISBN 0-8186-2735-2, S2CID 206437926.
  5. ^ 요한센, 얀, 랑게, 마틴(2003년),"CTL+ 이중 지수 시간에 대한 철저하다", Baeten, 조스 C.M.;Lenstra, 1월 카렐, Parrow, 요아힘, Woeginger, 게르하르트 J.(eds.), 30국제 콜로퀴움 오토마타에, 언어와 프로그래밍)(PDF), 강의 노트 컴퓨터 과학으로, 회보 2719주문 vol., Springer-Verlag,를 대신하여 서명함.767–775, doi:10.1007/3-540-45061-0_60, 아이 에스비엔 978-3-540-40493-4, 원본(PDF)에서 2007-09-30에 보관 시 2006-12-22 돌려받지 못 했다.
  6. ^ 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. pp. 39–50. doi:10.1007/978-3-540-70583-3_4.
  7. ^ Jussi Rintanen (2004). "Complexity of Planning with Partial Observability" (PDF). Proceedings of International Conference on Automated Planning and Scheduling. AAAI Press: 345–354.