NEXPTIME

계산 복잡도 이론에서 복잡도 종류 NEXPTIME (가끔 NEXP로 불림)은 시간 내에 비결정론적 튜링 기계로 풀 수 있는 결정 문제들의 집합이다.

NTIME 관점에서,

다른 방식으로, NEXPTIME은 검증자로 결정론적 튜링 기계를 사용하여 정의할 수 있다. 언어 L이 NEXPTIME에 속하는 것은 다항식 p와 q, 그리고 결정론적 튜링 기계 M이 존재하여 다음을 만족할 때이다.

우리는 다음을 알고 있다.

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

또한, 시간 위계 정리에 의해 다음을 알 수 있다.

NP ⊊ NEXPTIME

만약 P = NP라면, NEXPTIME = EXPTIME (패딩 논증); 더 정확히는, E ≠ NE일 때에만 P에 속하지 않는 희소 언어가 NP에 존재한다.

다른 특성화

서술 복잡도에서 NEXPTIME에서 인식될 수 있는 자연수의 집합은 정확히 어떤 논리 문장의 문장의 스펙트럼, 즉 유한 모델들의 크기 집합을 형성하는 것들이다.

NEXPTIME은 종종 대화형 증명 시스템의 맥락에서 발생하며, 여기에는 두 가지 주요 특징이 있다. 첫 번째는 MIP 증명 시스템인데, 여기에는 무한한 능력을 가진 두 명의 증명자(서로 통신하지 않음)가 무작위 다항 시간 검증자와 통신한다. 문자열이 언어에 있으면 높은 확률로 검증자를 확신시켜야 한다. 문자열이 언어에 없으면 낮은 확률을 제외하고는 검증자가 문자열을 수락하도록 공동으로 속일 수 없어야 한다. MIP 증명 시스템이 NEXPTIME의 모든 문제를 해결할 수 있다는 사실은 증명자가 한 명만 있을 때 PSPACE의 모든 문제를 인식할 수 있다는 점을 고려하면 상당히 인상적이다. 검증자가 두 증명자를 "교차 심문"하는 능력은 큰 힘을 부여한다. 자세한 내용은 대화형 증명 시스템#MIP을 참조하라.

NEXPTIME을 특징짓는 또 다른 대화형 증명 시스템은 특정 종류의 확률적으로 검사 가능한 증명이다. NP는 무한한 능력을 가진 증명자가 문자열이 언어에 있음을 증명하는 증거를 제시하고, 결정론적 다항 시간 기계가 그것이 유효한 증거임을 검증하는 문제들의 종류로 볼 수 있다. 이 설정에 두 가지 변화를 준다.

이 두 가지 확장은 함께 증명 시스템의 능력을 크게 확장하여 NEXPTIME의 모든 언어를 인식할 수 있게 한다. 이 클래스는 PCP(poly, poly)라고 불린다. 더 나아가, 이 특성화에서 검증자는 단지 상수 비트만 읽도록 제한될 수 있다. 즉, NEXPTIME = PCP(poly, 1)이다. 자세한 내용은 확률적으로 검사 가능한 증명을 참조하라.

NEXPTIME-완전

결정 문제는 NEXPTIME에 속하고, NEXPTIME의 모든 문제는 그것에 대한 다항 시간 다대일 환산이 있으면 NEXPTIME-완전이다. 다시 말해, 한 인스턴스를 같은 답을 가진 다른 인스턴스로 변환하는 다항 시간 알고리즘이 존재한다. NEXPTIME-완전 문제는 NEXPTIME에서 가장 어려운 문제로 생각할 수 있다. 우리는 NEXPTIME-완전 문제가 NP에 속하지 않는다는 것을 알고 있다. 이 문제들은 시간 위계 정리에 의해 다항 시간 내에 검증될 수 없다는 것이 증명되었다.

NEXPTIME-완전 문제의 예

간결한 문제

NEXPTIME-완전 문제의 중요한 집합은 간결한 회로와 관련이 있다. 간결한 회로는 그래프를 기하급수적으로 적은 공간으로 기술하는 데 사용되는 간단한 기계이다. 이들은 두 개의 정점 번호를 입력으로 받아 그들 사이에 에지가 있는지 여부를 출력한다. 인접행렬과 같은 자연스러운 표현으로 그래프 문제를 해결하는 것이 NP-완전이라면, 간결한 회로 표현으로 같은 문제를 해결하는 것은 NEXPTIME-완전이다. 왜냐하면 입력이 기하급수적으로 작기 때문이다 (NP-완전성 환산이 "투영"에 의해 달성된다는 약간의 조건 하에). 한 가지 간단한 예로, 그렇게 인코딩된 그래프의 해밀턴 경로를 찾는 것은 NEXPTIME-완전이다.

논리

두 변수를 가진 1차 논리의 만족성 문제는 NEXPTIME-완전이다. 계수와 두 변수를 가진 1차 논리의 만족성 문제는 NEXPTIME-완전이다.

게임

의존성 한정 이진 공식(DQBF, QBF의 불완전 정보 버전)에서 공식이 참인지 결정하는 것은 NEXPTIME-완전이다. 팀을 가진 제약 논리의 불완전 정보도 NEXPTIME-완전이다.

같이 보기

각주

  1. ↑ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library
  2. ↑ Jones, Neil D.; Selman, Alan L. (1974), “Turing machines and the spectra of first-order formulas”, 《J. Symb. Log.》 39 (1): 139–150, doi:10.2307/2272354, JSTOR 2272354, Zbl 0288.02021
  3. ↑ C. Papadimitriou & M. Yannakakis, A note on succinct representations of graphs, Information and control, vol 71 num 3, décember 1986, pp. 181—185, doi:10.1016/S0019-9958(86)80009-2
  4. ↑ C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.
  5. ↑ Etessami, Kousha; Vardi, Moshe Y.; Wilke, Thomas (2002년 12월 15일). 《First-Order Logic with Two Variables and Unary Temporal Logic》. 《Information and Computation》 179. 279–295쪽. doi:10.1006/inco.2001.2953. ISSN 0890-5401.
  6. ↑ Pratt-Hartmann, Ian (2014년 7월 14일). 〈Logics with counting and equivalence〉. 《Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)》. CSL-LICS '14. New York, NY, USA: Association for Computing Machinery. 1–10쪽. doi:10.1145/2603088.2603117. ISBN 978-1-4503-2886-9.
  7. ↑ Peterson, Gary L.; Reif, John H. (October 1979). 《Multiple-person alternation》. 《20th Annual Symposium on Foundations of Computer Science (sfcs 1979)》. 348–363쪽. doi:10.1109/SFCS.1979.25.
  8. ↑ Hearn, Robert Aubrey (2006). 《Games, puzzles, and computation》 (학위논문). USA: Massachusetts Institute of Technology.