NEXPTIME

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

NTIME 관점에서,

다른 방식으로, NEXPTIME은 검증자로 결정론적 튜링 기계를 사용하여 정의할 수 있다. 언어 L이 NEXPTIME에 속하는 것은 다항식 p와 q, 그리고 결정론적 튜링 기계 M이 존재하여 다음을 만족할 때이다.
 모든 x와 y에 대해, 기계 M은 입력 에 대해  시간 내에 실행된다.
 L에 속하는 모든 x에 대해, 길이 의 문자열 y가 존재하여 을 만족한다.
 L에 속하지 않는 모든 x와 길이 의 모든 문자열 y에 대해, 을 만족한다.
우리는 다음을 알고 있다.

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

만약 라면,  (패딩 논증); 더 정확히는, E ≠ NE일 때에만 P에 속하지 않는 희소 언어가 NP에 존재한다.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

 다른 특성화 
서술 복잡도에서 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-완전성 환산이 "투영"에 의해 달성된다는 약간의 조건 하에).C. Papadimitriou & M. Yannakakis, A note on succinct representations of graphs, Information and control, vol 71 num 3, décember 1986, pp. 181—185, C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. . Section 20.1, pg.492. 한 가지 간단한 예로, 그렇게 인코딩된 그래프의 해밀턴 경로를 찾는 것은 NEXPTIME-완전이다.

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

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

 같이 보기 
 게임 복잡도
 NP
 EXPTIME

 각주 

 , 


분류:복잡도 종류