디타임

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

리소스 DTIME은 일정량의 계산 시간을 사용하여 해결할 수 있는 모든 의사결정 문제의 집합인 복잡성 클래스를 정의하기 위해 사용된다.If a problem of input size n can be solved in ${\displaystyle O(f(n))}$, we have a complexity class ${\displaystyle {\mathsf {DTIME}}(f(n))}$ (or ${\displaystyle {\mathsf {TIME}}(f(n))}$).사용되는 메모리 공간의 양에는 제한이 없지만, 다른 일부 복잡성 자원(대체 등)에는 제한이 있을 수 있다.

DTIME의 복잡성 클래스

많은 중요한 복잡성 등급은 DTIME의 관점에서 정의되며, 일정한 결정론적 시간 내에 해결될 수 있는 모든 문제를 포함하고 있다.모든 적절한 복잡성 함수는 복잡성 등급을 정의하는 데 사용될 수 있지만, 특정 클래스만 연구하는데 유용하다.일반적으로, 우리는 우리의 복잡성 클래스가 계산 모델의 변화에 대해 견고하게 되고 서브루틴의 구성 하에서 닫히기를 원한다.

DTIME은 시간 계층의 정리를 만족시키며, 이는 무증상적으로 더 큰 시간의 양이 항상 엄밀히 더 큰 문제 집합을 만든다는 것을 의미한다.

잘 알려진 복잡도 등급 P는 다항식 DTIME 양으로 해결할 수 있는 모든 문제를 구성한다. 이는 공식적으로 다음과 같이 정의될 수 있다.

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

P는 선형 시간 문제 $D{\displaystyle \mathsf{}}$ T ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{M}}$ ${\displaystyle \mathsf{E}}$ ${\displaystyle (n}$ ${\displaystyle )}$ ${\$AMS 2004, 강의 2.2, 페이지 20)을 포함하는 가장 작은 강건한 등급이다.P는 "컴퓨터적으로 실현 가능한" 것으로 간주되는 가장 큰 복잡성 등급 중 하나이다.

결정론적 시간을 사용하는 훨씬 더 큰 클래스는 EXPTIME으로, 지수적 시간에 결정론적 기계를 사용하여 해결할 수 있는 모든 문제를 포함하고 있다.공식적으로, 우리는

${\displaystyle {\mathsf {EXPTIME}=\bigcup _{k\in \mathb{N}}{{\mathsf{DTIME}}}}{{n^{k}\오른쪽).}$

더 큰 복잡성 등급은 유사하게 정의될 수 있다.시간 계층 정리 때문에 이러한 클래스들은 엄격한 계층 구조를 형성한다; $우리$는 P ${\displaystyle ⊊}$ E ${\displaystyle X\mathsf{}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle \mathsf{T}}$ ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{M}}$ ${\displaystyle \mathsf{E}}$ ${\${\$mathsf {EXPTIME$ 그리고 그 이상이라고 알고 있다.

기계 모델

DTIME을 정의하는 데 사용되는 정확한 기계 모델은 자원의 힘에 영향을 미치지 않고 달라질 수 있다.문헌의 결과는 특히 매우 작은 시간 클래스에 대해 논의할 때 멀티테이프 튜링 기계를 사용하는 경우가 많다.특히 멀티테잎 결정론적 튜링 기계는 절대로 싱글렛테이프 기계에 비해 2차 시간 속도를 높일 수 없다.^[1]

사용된 시간의 양에서 곱셈 상수는 DTIME 클래스의 힘을 바꾸지 않는다; 항상 일정한 곱셈 속도 상승은 유한 상태 제어에서 상태 수를 증가시킴으로써 얻을 수 있다.파파디미트리오의 성명에서 ^[2]L언어로는

$L{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle D\mathsf{}}$ T ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{M}}$ ${\displaystyle \mathsf{E}}$( ${\displaystyle f}$( )${\displaystyle L\in {\mathsf$ {$DTIME}(f(n)})}$을(를) 놓으십시오$.$Then, for any ${\displaystyle \epsilon >0}$, ${\displaystyle L\in {\mathsf {DTIME}}(f'(n))}$, where ${\displaystyle f'(n)=\epsilon f(n)+n+2}$.

일반화

결정론적 튜링 머신 이외의 모델을 사용하면 DTIME의 일반화 및 제약이 다양하다. 예를 들어 비결정론적 튜링 머신을 사용하면 자원 NTIME이 있다.DTIME의 표현력과 다른 계산 자원의 관계는 매우 잘 이해되지 않는다.알려진 몇 안 되는 결과^[3] 중 하나는

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

다중 테이프 시스템용이것은 까지 연장되었다.

${\displaystyle {\mathsf {DTIME}(O(n{\sqrt {\log ^{*n}))\neq {\mathsf {NTIME}(O(n{\sqrt {\log ^{*n})})}}$

산담으로^[4]

만약 우리가 교대 튜링 기계를 사용한다면, 우리는 ATIME 자원을 가지고 있다.

참조

• American Mathematical Society (2004). Rudich, Steven and Avi Wigderson (ed.). Computational Complexity Theory. American Mathematical Society and Institute for Advanced Study. ISBN 0-8218-2872-X.
• Papadimitriou, Christos H. (1994). Computational Complexity. Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.