NEXPTIME

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

NTIME 관점에서,

{\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})

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

모든 x와 y에 대해, 기계 M은 입력 $(x,y)$ 에 대해 $2^{p(|x|)}$ 시간 내에 실행된다.
L에 속하는 모든 x에 대해, 길이 $2^{q(|x|)}$ 의 문자열 y가 존재하여 $M(x,y)=1$ 을 만족한다.
L에 속하지 않는 모든 x와 길이 $2^{q(|x|)}$ 의 모든 문자열 y에 대해, $M(x,y)=0$ 을 만족한다.

우리는 다음을 알고 있다.

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

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

NP ⊊ NEXPTIME

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

다른 특성화

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

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-완전성 환산이 "투영"에 의해 달성된다는 약간의 조건 하에).^[3]^[4] 한 가지 간단한 예로, 그렇게 인코딩된 그래프의 해밀턴 경로를 찾는 것은 NEXPTIME-완전이다.

논리

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

게임

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

같이 보기

각주

↑ 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
↑ 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
↑ 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
↑ C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.
↑ 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.
↑ 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.
↑ 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.
↑ Hearn, Robert Aubrey (2006). 《Games, puzzles, and computation》 (학위논문). USA: Massachusetts Institute of Technology.

컴플렉시티 주: NEXP, 컴플렉시티 주: coNEXP
Arora, Sanjeev; Barak, Boaz (2009), 《Computational Complexity: A Modern Approach》, Cambridge, 57쪽, ISBN 978-0-521-42426-4

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v t e 주요 복잡도 종류 (더 보기)
실현 가능	L NL NC P P-완전 ZPP RP BPP BQP
실현 불가능 (추측)	PCP UP SNP NP NP-완전 NP-난해 co-NP co-NP-완전 PH #P #P-완전 PSPACE=IP PSPACE-완전
실현 불가능	EXPTIME EXPSPACE PR R RE RE-완전 co-RE co-RE-완전