DTIME

계산 복잡도 이론에서 DTIME 또는 TIME은 결정론적 튜링 기계의 연산 시간 연산 자원이다. 이는 "일반적인" 물리 컴퓨터가 특정 알고리즘을 사용하여 특정 계산 문제를 해결하는 데 걸리는 시간(또는 계산 단계 수)을 나타낸다. 이는 중요한 실제 자원(컴퓨터가 문제를 해결하는 데 걸리는 시간)과 매우 밀접하게 관련되어 있기 때문에 가장 잘 연구된 복잡성 자원 중 하나이다.

DTIME 자원은 특정 양의 연산 시간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 입력 크기 n의 문제가 $O(f(n))$으로 해결될 수 있다면, 복잡도 종류 ${\mathsf {DTIME}}(f(n))$ (또는 ${\mathsf {TIME}}(f(n))$)를 가진다. 사용되는 메모리 공간의 양에는 제한이 없지만, 다른 복잡성 자원(예: 교대)에는 제한이 있을 수 있다.

DTIME의 복잡도 종류

많은 중요한 복잡도 종류는 DTIME으로 정의되며, 특정 양의 결정론적 시간으로 해결할 수 있는 모든 문제를 포함한다. 모든 적절한 복잡도 함수를 사용하여 복잡도 종류를 정의할 수 있지만, 특정 종류만 연구하는 데 유용하다. 일반적으로, 우리는 복잡도 종류가 계산 모델의 변화에 대해 견고하고, 서브루틴의 구성에 대해 닫혀 있기를 원한다.

DTIME은 시간 계층 정리를 만족하며, 이는 점근적으로 더 많은 양의 시간이 항상 엄격하게 더 큰 문제 집합을 생성한다는 것을 의미한다.

잘 알려진 복잡도 종류 P는 다항식 시간 DTIME으로 해결할 수 있는 모든 문제를 포함한다. 이는 공식적으로 다음과 같이 정의할 수 있다.

${\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})$

P는 선형 시간 문제 ${\mathsf {DTIME}}\left(n\right)$를 포함하는 가장 작은 견고한 종류이다 (AMS 2004, Lecture 2.2, pg. 20). P는 "계산적으로 실현 가능한" 것으로 간주되는 가장 큰 복잡도 종류 중 하나이다.

결정론적 시간을 사용하는 훨씬 더 큰 종류는 EXPTIME이며, 이는 지수 시간에 결정론적 기계로 해결할 수 있는 모든 문제를 포함한다. 공식적으로, 우리는 다음을 얻는다.

${\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right).$

더 큰 복잡도 종류도 비슷하게 정의할 수 있다. 시간 계층 정리 때문에, 이들 종류는 엄격한 계층 구조를 형성한다; 우리는 ${\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}$임을 알고 있으며, 그 이상도 마찬가지다.

기계 모델

P와 같은 견고한 종류의 경우, DTIME을 정의하는 데 사용되는 정확한 기계 모델은 자원의 성능에 영향을 주지 않으면서 변경될 수 있다. 계산 복잡성 문헌은 특히 매우 작은 시간 종류를 논의할 때 다중 테이프 튜링 기계를 기반으로 DTIME을 정의하는 경우가 많다. 다중 테이프 결정론적 튜링 기계는 단일 테이프 기계보다 2차 시간 가속을 제공할 수 없다.

튜링 기계의 선형 속도 향상 정리 때문에, 시간 경계의 곱셈 상수는 DTIME 종류의 범위에 영향을 주지 않는다; 유한 상태 제어의 상태 수를 늘리고 테이프 알파벳의 크기를 늘림으로써 항상 상수 곱셈 속도 향상을 얻을 수 있다. 파파디미트리우의 진술에서, 언어 L에 대해,

Let $L\in {\mathsf {DTIME}}(f(n))$. Then, for any $\epsilon >0$, $L\in {\mathsf {DTIME}}(f'(n))$, where $f'(n)=\epsilon f(n)+n+2$.

일반화

결정론적 튜링 기계 이외의 모델을 사용하면 DTIME의 다양한 일반화 및 제한이 있다. 예를 들어, 비결정론적 튜링 기계를 사용하면 NTIME 자원을 얻는다. DTIME과 다른 계산 자원의 표현력 간의 관계는 거의 이해되지 않고 있다. 몇 안 되는 알려진 결과 중 하나는 다음과 같다.

${\mathsf {DTIME}}(O(n))\neq {\mathsf {NTIME}}(O(n))$

다중 테이프 기계의 경우. 이것은 Santhanam에 의해 다음으로 확장되었다. 여기서 $\log ^{*}n$은 반복 로그이다.

교대 튜링 기계를 사용하면 ATIME 자원을 얻는다.

각주

• [[American Mathematical Society|미국 수학회]] (2004). 스티븐 루디치 and 아비 위그더슨 (편집). 《Computational Complexity Theory》. 미국 수학회 and 프린스턴 고등연구소. ISBN 0-8218-2872-X. 
• [[크리스토스 파파디미트리우|Papadimitriou, Christos H.]] (1994). 《Computational Complexity》. Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.