시간 계층 정리

계산 복잡성 이론에서 시간 계층 구조 이론은 튜링 기계에 대한 시간 경계 계산에 관한 중요한 진술이다.비공식적으로, 이러한 이론들은 더 많은 시간이 주어지면 튜링 기계가 더 많은 문제를 해결할 수 있다고 말한다.예를 들어 n시간으로는² 해결할 수 있지만 n시간으로는 해결할 수 없는 문제가 있다.

결정론적 다중 테이프 튜링 기계의 시간 계층 정리는 리처드 E에 의해 처음 입증되었다. 1965년 스턴스와 쥬리스 하트마니스.^[1]1년 후 F. C. Hennie와 Richard E가 개선되었다.스턴스는 유니버설 튜링 기계의 효율을 향상시켰다.^[2]그 결과, 정리에 따라 결정론적 시간경계 복잡도 등급마다 엄격히 더 큰 시간경계 복잡도 등급이 존재하므로 시간경계 복잡도 등급의 계층이 완전히 붕괴되지는 않는다.더 정확히 말하면, 결정론적 튜링 기계의 시간 계층 구조 정리는 모든 시간 구성 함수 f(n)에 대해,

${\displaystyle {\mathsf {DTIME}}\left(o\left({\frac {f(n)}{\log f(n)}}\right)\right)\subsetneq {\mathsf {DTIME}}(f(n))}$.

비결정론적 튜링 기계의 시간 계층 정리는 원래 1972년 스티븐 쿡에 의해 증명되었다.^[3]1978년 조엘 세이퍼스, 마이클 피셔, 알버트 마이어의 복잡한 증거를 통해 현재의 형태로 개선되었다.^[4]마침내 1983년 스타니슬라프 ž크는 오늘날 가르쳐진 간단한 증거로 같은 결과를 얻었다.^[5]비결정론적 튜링 기계에 대한 시간 계층 구조 정리에서는 g(n)가 시간 구성 가능한 함수라면 f(n+1) = o(g(n))라고 기술하고 있다.

${\displaystyle \mathsf{N}}$ ${\displaystyle \mathsf{T}}$ ${\displaystyle \mathsf{I}}$ M ${\displaystyle \mathsf{E}}$( f${\displaystyle }$( ${\displaystyle n}$)${\displaystyle }$) ${\displaystyle ⊊}$ ${\displaystyle N\mathsf{}}$ ${\displaystyle \mathsf{T}}$ I ${\displaystyle \mathsf{M}}$ E${\displaystyle }$( ${\displaystyle g}$ )${\displaystyle }${ {${\displaystyle }${ { { { { { ${$ { { { { { { { { { \\$mathsf {NTIME}}(f(n)\subsetneq {\mathsf{NTIME$

우주에 대한 유사한 이론은 우주 계층 구조 이론이다.유사한 정리는 시간경계 확률론적 복잡성 세분류에 대해서는 알 수 없다. 단, 클래스에도 약간의 조언이 있지 않는 한 말이다.^[6]

배경

두 이론 모두 시간 구성 가능한 함수의 개념을 사용한다.A function ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ is time-constructible if there exists a deterministic Turing machine such that for every ${\displaystyle n\in \mathbb {N} }$, if the machine is started with an input of n ones, it will halt after precisely f(n) steps.음수가 아닌 정수 계수가 있는 모든 다항식은 2와ⁿ 같은 지수함수와 마찬가지로 시간구성이 가능하다.

증명 개요

우리는 어떤 시간 클래스 TIME(g(n))이 어떤 시간 클래스 TIME(f(n))보다 확실히 크다는 것을 증명할 필요가 있다.우리는 TIME(f(n))에 있을 수 없는 기계를 대각선으로 건설하여 이것을 한다.그런 다음 시뮬레이터 기계를 사용하여 기계가 TIME(g(n))에 있음을 보여 준다.

결정론적 시간 계층 정리

성명서

시간 계층 정리.f(n)가 시간 구성 가능한 함수라면 최악의 경우 결정론적 시간 f(n)에서는 해결할 수 없지만 최악의 경우 결정론적 시간 f(n)에서는 해결할 수 있는 의사결정 문제가 존재한다.²바꾸어 말하면, 환언하면

${\displaystyle {\mathsf {DTIME}(f)(n)\subsetneq {\mathsf {DTIME}\f(n)^{2}\right.}$

주 1.f(n)는 최소 n이다. 작은 함수는 결코 시간 구성 가능한 것이 아니기 때문이다.

주 2. 더 일반적으로는 f(n)가 시간구축이 가능하다면 그 다음이라는 것을 알 수 있다.

${\displaystyle {\mathsf {DTIME}\좌측(o\frac {f(n)}{\log f(n)}}\우측)\subsetneq {\mathsf {DTIME}\좌측(f(n)\우측)\우측).}$

예를 들어, 시간 n에는 해결² 가능한 문제가 있지만 시간 n에는 해결이 되지 않는다. n은 다음 위치에 있기 때문이다.

${\displaystyle o\left({\frac{n^{2}}:{n^{2}}:}\오른쪽).}$

증명

DTIME(f(n))이 DTIME(2n ³+ 1)의 엄격한 하위 집합이라는 증거를 여기에 포함시킨다.증거를 f(n)로 확장하는 방법에 대한 자세한 내용은 이 섹션의 하단을 참조하십시오.²

이를 증명하기 위해, 우리는 먼저 기계의 인코딩 언어와 기계의 입력을 f 내에서 멈추게 하는 것을 정의한다.

${\displaystyle H_{f}=\left\{([M],x)\\\M\text{accepts}\\\\text{in}\f(x )\\\\\text{step}\right\}.}$

이것은 시간급이라는 것을 여기서 주목해라.기계 M이 f( x ) 단계 내에서 수용하도록 기계 쌍과 기계에 대한 입력(M,x)의 집합이다.

여기서 M은 결정론적 튜링 기계로, x는 그 입력(테이프의 초기 내용)이다.[M]은 튜링 머신 M을 인코딩하는 입력을 의미한다.tuple ([M], x)의 크기가 되게 한다.

우리는 결정론적 튜링 기계 R을 통해 H의_f 멤버십을 결정할 수 있다는 것을 알고 있다. 이 기계는 f(x) 단계의 M을 먼저 계산한 다음 그 길이의 0s 행을 작성한 다음 이 0의 행을 "클록" 또는 "카운터"로 사용하여 그 많은 스텝에서 M을 시뮬레이션한다.각 단계에서 시뮬레이션 기계는 다음 동작이 무엇인지 결정하기 위해 M의 정의를 훑어볼 필요가 있다.이 작업에는 최대 f(m)³ 조작이 필요하다고 해도 무방하다(시간 복잡도 T(TlogT)에서 시간 복잡도 T(n)의 시뮬레이션을 달성할 수 있다는 것을 알기 때문에, 우리는 다음과 같은 것을 가지고 있다.

${\displaystyle H_{f}\in {\mathsf {TIME}\왼쪽(f(m)^{3}\오른쪽).}$

나머지 증거들은 다음과 같은 것을 보여줄 것이다.

${\displaystyle H_{f}\notin {\mathsf {TIME}\좌측(\f\floor {\floor {\frack}{2}}\오른쪽)}$

그래서 만약 우리가 2n + 1을 m으로 대체한다면, 우리는 원하는 결과를 얻을 수 있다.H가_f 이 시간 복잡도 등급에 있다고 가정해 보자, 그러면 우리는 모순에 도달할 것이다.

H가_f 이 시간 복잡도 등급인 경우 기계 K가 존재하며, 기계 설명 [M]과 입력 x에 따라 튜플([M], x)이_f H 내에 있는지 여부를 결정한다.

${\displaystyle {\mathsf {TIME}\좌측(f\좌측(\floor{m}{{2}}\우측)\우측)).}$

우리는 이 K를 다른 기계인 N을 만들 때 사용한다. N은 기계 설명 [M]을 받아서 Tuple ([M], [M])에서 K를 실행한다.M은 K에 의해 자체 코드로 시뮬레이션되고, 그 다음 K가 거부하면 N이 받아들이고, K가 거부하면 거부한다.n이 N에 대한 입력의 길이인 경우 m(K에 대한 입력의 길이)은 2배 n + 일부 구분 기호 기호이므로 m = 2n + 1. N의 실행 시간은 다음과 같다.

${\displaystyle {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {2n+1}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f(n)\right).}$

이제 우리가 N 자체에 입력으로 [N]을 공급하고(이 입력은 [N]의 길이를 만든다) N이 자신의 설명을 입력으로 받아들이는지 여부를 묻는다면, 우리는 다음을 얻는다.

• If N accepts [N] (which we know it does in at most f(n) operations since K halts on ([N], [N]) in f(n) steps), this means that K rejects ([N], [N]), so ([N], [N]) is not in H_f, and so by the definition of H_f, this implies that N does not accept [N] in f(n) steps.모순.

• N이 [N](대부분 f(n) 연산에서 하는 것으로 알고 있음)을 거부하면, 이는 K가 ([N]), [N]을 받아들이므로 ([N]), ([N])이 H에_f 있고, 따라서 N은 (n) 단계로 [N]을 수용한다는 것을 의미한다.모순.

따라서 K 기계는 존재하지 않는다고 결론짓고, 그래서

${\displaystyle H_{f}\notin {\mathsf {TIME}\왼쪽(\f\floor {\floor {\floor \오른쪽)\오른쪽).}$

확장

독자는 증거가 간단하다는 것을 깨달았을지도 모른다. 왜냐하면 우리는 우리가 확신할 수 있는 간단한 튜링 머신 시뮬레이션을 선택했기 때문이다.

${\displaystyle H_{f}\in {\mathsf {TIME}(f(m)^{3})).}$

보다 효율적인 시뮬레이션 모델이 존재한다는 것이 증명되었으며^[7], 이 모델은 다음과 같다.

${\displaystyle H_{f}\in {\mathsf {TIME}(f(m)\log f(m)}$

그러나 시뮬레이션의 이 모델은 오히려 여기에 포함되지 않는다.

그러나 위와 동일한 인수가 ${\displaystyle D}$ ${\displaystyle T}$ ${\displaystyle I}$ M ${\displaystyle E}$( r${\displaystyle }$( (${\displaystyle \mathrm{f}}$ (${\displaystyle 2}$ m${\displaystyle }$+ 1 ) $))$ {\$displaystyle$DTIME$(r$ ($f$(2m$+$$1$)))을 의미한다는 점을 관찰하십시오.$}$ is not contained within ${\displaystyle DTIME(f(m))}$ if ${\displaystyle r(f( M + x ))}$ is a function which gives a time within which it is possible to simulate a machine ${\displaystyle M}$ with time complexity ${\displaystyle f(n)}$ on input ${\d$$isplaystyle x}$.

비결정적 시간 계층 정리

g(n)가 시간구축함수이고 f(n+1) = o(n)이면 비결정적 시간 f(n)에서는 풀 수 없지만 비결정적 시간 g(n)에서는 풀 수 있는 의사결정 문제가 존재한다.즉, 복잡도 등급 NTIME(f(n)은 NTIME(g(n))의 엄격한 하위 집합이다.

결과들

시간 계층 구조 이론은 지수 계층의 결정론적 및 비결정론적 버전이 진정한 계층임을 보장한다. 즉, P ⊊ EXPTIME ⊊ 2-EXP ⊊ …과 NP ⊊ NEXPTIME ⊊ 2-NEXP .... ....

For example, ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}$ since ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}}$. Indeed, ${\displaystyle \mathsf{D}}$${\displaystyle {\mathsf {DTIME}}\left(2^{n}\right)\subseteq {\mathsf {DTIME}}\left(o\left({\frac {2^{2n}}{2n}}\right)\right)\subsetneq {\mathsf {DTIME}}(2^{2n})}$ from the time hierarchy theorem.

또한 이 정리는 P에 임의로 큰 지수를 요구하는 문제가 있음을 보장한다. 즉, P는 고정 k에 대해 DTIME(n^k)로 붕괴되지 않는다.예를 들어, n시간에는⁵⁰⁰⁰ 해결할 수 있는 문제가 있지만⁴⁹⁹⁹ n시간에는 해결할 수 없다.이것은 P가 알고리즘의 실제적인 클래스라는 관습인 코브햄의 논문에 반대하는 하나의 주장이다.만약 그러한 붕괴가 일어났다면, 우리는 DTIME(f(n))이 DSPACE(f(n))에 엄격히 포함되어 있다는 것이 잘 알려진 정리인 만큼, P space PSPACE를 추론할 수 있을 것이다.

그러나 시간 계층 구조 이론은 결정론적 복잡성과 비결정론적 복잡성 또는 시간과 공간의 복잡성을 연관시킬 수단을 제공하지 않기 때문에, 계산 복잡성 이론의 위대한 미해결 문제 즉 P와 NP, NP와 PSPACE, PSPACE와 EXPTIME 또는 EXPTIME과 NEXPTIME이 동일한지 여부에 대해서는 빛을 발하지 않는다.

참고 항목

• 공간 위계 정리

참조

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 9.1절의 310~313페이지: 계층 구조 정리
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. 제7.2절: 위계 정리, 페이지 143–146.