엑스포스페이스

계산 복잡성 이론에서 EXPSPACE는 지수적 공간의 결정론적 튜링 ${\displaystyle {시스템}^{}}$에 의해 해결 가능한 모든 의사결정 문제의 집합이다. 즉, $O{\displaystyle }$( 2 ${\displaystyle {\mathrm{}}^{}}$(${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle O (2^{p(n)}}$ 공간$$, $여기$서${\displaystyle }$p ( n$$) ${\$$displaystyp$ p($n$$)}$은 $}$의 다항함수 기능이다$.$ 일부 저자는 ${\displaystyle p}$를 제한한다${\displaystyle .}$${\displaystyle )}$ ${\displaystyle p(n)}$은(는) 선형 함수가 되려고$$ 하지만 대부분의 저자는 대신 결과 클래스 ESPACE를 부른다.대신 비결정론적 기계를 사용하면 사비치의 정리로는 EXPSPACE에 해당하는 NEXPSPACE 클래스가 나온다.

결정문제는 EXPSPACE-완전한 경우 EXPSPACE이다. EXPSPACE의 모든 문제는 다항식 시간 다수를 1로 줄인다.즉, 같은 대답으로 하나의 인스턴스를 다른 인스턴스로 변환하는 다항식 시간 알고리즘이 있다.EXPSPACE-완전한 문제는 EXPSPACE에서 가장 어려운 문제로 생각될 수 있다.

EXPSPACE는 PSpace, NP, P의 엄격한 상위 집합으로 EXPTIME의 엄격한 상위 집합으로 여겨진다.

형식 정의

DSPACE와 NSPACE의 관점에서 보면,

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}\left(2^{n^{k}}\right)=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)}$

문제의 예

EXPSPACE-완전한 문제의 예로는 두 개의 정규 표현이 서로 다른 언어를 나타내는지를 인식하는 문제가 있는데, 여기서 표현은 연합, 결합, 클레인 별(표현 0개 이상), 스퀴링(표현 2개 사본)^[1]의 네 개의 연산자로 제한된다.

클레인 별이 빠지면 그 문제는 NEXPTIME-완전성이 되는데,^{[citation needed]} 이는 결정론적이라기보다는 비결정론적 튜링 기계의 관점에서 정의된다는 점을 제외하면 EXPTIME-완전성과 같다.

1980년 L. Berman에 의해서도 덧셈과 비교만을 수반하는 실수에 관한 1차 진술의 검증/확인의 문제가 EXPSPACE에 있다는 것이 증명되었다.

Alur와 Henzinger는 시간(integer)으로 Linear temporary logic을 확장했고, 그들의 논리의 타당성 문제가 EXPSPACE-완전하다는 것을 증명한다.^[2]

페트리 네트의 커버빌리티 문제는 EXPSPACE-완전하다.^[3][4]페트리 그물에 대한 도달성 문제는 오랫동안 EXPSPACE-hard인 것으로 알려져 있었지만,^[5] 비원소적인 것으로 나타나기 때문에 EXPSPACE에서는 확실히 그렇지 않다.^[6]

타계급과의 관계

EXPSPACE는 PSpace, NP, P의 엄격한 상위 집합으로 알려져 있다.더 나아가 EXPTIME의 엄격한 슈퍼셋으로 의심되지만, 이것은 알려지지 않았다.

참고 항목

• 게임 복잡성

참조

• Berman, Leonard (1 May 1980). "The complexity of logical theories". Theoretical Computer Science. 11 (1): 71–77. doi:10.1016/0304-3975(80)90037-7.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 제9.1.1절: 지수 공간 완전성, 페이지 313–317.지수를 사용한 정규식 등가성을 결정하는 것이 EXPSPACE-완전하다는 것을 증명한다.