DTIME

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

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

DTIME의 복잡도 종류

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

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

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

𝖯 = ⋃_{k \in ℕ} 𝖣 𝖳 𝖨 𝖬 𝖤 (n^{k})

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

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

𝖤 𝖷 𝖯 𝖳 𝖨 𝖬 𝖤 = ⋃_{k \in ℕ} 𝖣 𝖳 𝖨 𝖬 𝖤 (2^{n^{k}}) .

더 큰 복잡도 종류도 비슷하게 정의할 수 있다. 시간 계층 정리 때문에, 이들 종류는 엄격한 계층 구조를 형성한다; 우리는 $𝖯 ⊊ 𝖤 𝖷 𝖯 𝖳 𝖨 𝖬 𝖤$ 임을 알고 있으며, 그 이상도 마찬가지다.

기계 모델

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

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

Let

L \in 𝖣 𝖳 𝖨 𝖬 𝖤 (f (n))

. Then, for any

ϵ > 0

,

L \in 𝖣 𝖳 𝖨 𝖬 𝖤 (f^{'} (n))

, where

f^{'} (n) = ϵ f (n) + n + 2

.

일반화

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

𝖣 𝖳 𝖨 𝖬 𝖤 (O (n)) \neq 𝖭 𝖳 𝖨 𝖬 𝖤 (O (n))

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

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

각주

↑ Papadimitriou 1994, Thrm. 2.1
↑ 1994, Thrm. 2.2
↑ Paul Wolfgang, 닉 피핑어, 세메레디 엔드레, William Trotter. On determinism versus non-determinism and related problems. 24th Annual Symposium on Foundations of Computer Science, 1983. doi:10.1109/SFCS.1983.39
↑ Rahul Santhanam, On separators, segregators and time versus space, 16th Annual IEEE Conference on Computational Complexity, 2001.

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

[1] Papadimitriou 1994, Thrm. 2.1

[2] 1994, Thrm. 2.2

[3] Paul Wolfgang, 닉 피핑어, 세메레디 엔드레, William Trotter. On determinism versus non-determinism and related problems. 24th Annual Symposium on Foundations of Computer Science, 1983. doi:10.1109/SFCS.1983.39

[4] Rahul Santhanam, On separators, segregators and time versus space, 16th Annual IEEE Conference on Computational Complexity, 2001.

[1]

[2]

[3]

[4]

v t e 복잡도 종류
효율적 해결 가능	DLOGTIME AC⁰ ACC⁰ REG TC TC⁰ L SL RL FL NL NL-완전 NC SC CC P P-완전 ZPP RP BPP BQP APX FP
비효율적 추정	UP NP NP-완전 NP-난해 Co-NP Co-NP-완전 TFNP FNP AM QMA PH ⊕P PP #P #P-완전 IP PSPACE PSPACE-완전
효율적 해결 불가능	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY NONELEMENTARY PR R RE ALL
기타 복잡도 종류	polyL QP
종류별 위계	다항 위계 지수 위계 그르제고르치크 위계 산술적 위계 불리언 위계
복잡도 계열	DTIME NTIME DSPACE NSPACE PCP 대화형 증명 시스템
복잡도 종류 목록