DLOGTIME

계산 복잡도 이론에서 DLOGTIME은 결정론적 튜링 기계에서 로그 단위의 계산 시간 안에 해결할 수 있는 모든 계산 문제의 복잡도 종류이다. 이 정의는 임의 접근(random-access)이 가능한 튜링 기계에서 정의되어야 하는데, 그렇지 않으면 입력 테이프가 기계가 접근할 수 있는 셀의 범위보다 길기 때문이다. 이는 시간 복잡도의 관점에서 매우 약한 모델이다. 즉, 더 작은 결정론적 시간 제한을 가진 임의 접근 튜링 기계로는 전체 입력에 접근할 수 없다.

DLOGTIME 기계가 그대로 사용되는 경우는 드물다. 대신, 이들은 대개 귀약 가능성을 연구하기 위한 이론적 구성의 일부로 사용된다. 이 기계들은 로그 길이보다 긴 출력을 생성하는 데 사용할 수 없다. 그러나 다음과 같은 방식으로 간접적으로 그러한 출력을 생성하는 데 사용될 수 있다. 임의의 로그 길이 이진 주소가 주어지면, 해당 출력 비트를 생성하는 것이다. 다항 크기의 정수는 로그 길이의 이진 표현을 가지므로, 이는 DLOGTIME에서 가능하다.

정의

다음 테이프를 가진 결정론적 튜링 기계를 고려하자.^: 140

• 읽기 전용 입력 테이프.
• 읽고 쓸 수 있는 주소 테이프.
• 읽고 쓸 수 있는 작업 테이프.

기계는 다음과 같은 방식으로만 입력 테이프에서 읽을 수 있다: "읽기" 상태로 전이한 다음, 다음 시간 단계에서 주소 테이프에 있는 이진 주소에 해당하는 인덱스의 입력 테이프 비트를 받는다.

DLOGTIME은 입력의 길이를 ${\displaystyle n}$이라 할 때, 이러한 기계로 ${\displaystyle O(\log n)}$ 시간 안에 해결할 수 있는 결정 문제의 종류이다.

예시

DLOGTIME은 "입력의 길이가 짝수인가?"와 같이 입력의 길이를 검증하는 것과 관련된 일부 문제를 해결할 수 있으며, 이는 이진 검색을 사용하여 로그 시간 내에 해결할 수 있다.

더 일반적으로, 임의의 ${\displaystyle p\geq 1}$와 정수 ${\displaystyle k}$에 대하여, ${\displaystyle |x|\equiv k\mod p}$인지 결정할 수 있다. 이는 이진 검색을 사용하여 작업 테이프에 ${\displaystyle |x|}$의 이진 표현을 먼저 변환한 다음, 튜링 기계의 상태 전이 표에 저장된 참조 표를 사용하여 mod-p 상태를 추적하며 이진 표현을 비트 단위로 살펴봄으로써 수행된다.

DLOGTIME으로 결정 가능한 문제들의 집합은 유한 합집합, 유한 교집합, 그리고 부정 연산에 대해 닫혀 있다.

변환기

DLOGTIME 기계에 출력 테이프를 제공할 수 있지만, 이 경우 ${\displaystyle O(\log n)}$ 비트만을 출력할 시간이 주어진다. 이를 통해 길이 ${\displaystyle n}$의 시퀀스에서 길이 ${\displaystyle O(\log n)}$의 시퀀스로의 시퀀스 변환을 수행할 수 있다.

더 긴 시퀀스로의 변환을 수행하기 위해, 로그 공간 귀약에서도 사용되는 표준적인 기법을 통해 암묵적 변환을 정의할 수 있다.

함수 ${\displaystyle f:2^{*}\to 2^{*}}$가 암묵적으로 DLOGTIME 계산 가능하다는 것은 다음을 의미한다:^: 140

• 다항식으로 제한됨: 모든 ${\displaystyle x\in 2^{*}}$에 대하여 ${\displaystyle f(x)\leq |x|^{c}}$를 만족하는 ${\displaystyle c>0}$이 존재한다.
• ${\displaystyle L_{f}=\left\{\langle x,i,c\rangle \mid f(x)_{i}=c\right\}}$가 DLOGTIME-결정 가능함.

이것은 불리언 회로 군의 DLOGTIME-계산을 정의할 수 있게 한다.

참고: DLOGTIME 기계는 입력에서 ${\displaystyle O(\log n)\ll n}$ 개의 항목만 확인할 시간이 있으므로, 보통 함수 ${\displaystyle f}$의 입력을 단항 입력으로 제한해야 한다. 즉, 사소한 실패를 피하기 위해 함수의 입력은 오직 ${\displaystyle \epsilon ,1,11,111,\dots }$일 수 있다.

회로 복잡도

DLOGTIME-균일성은 회로 복잡도에서 사용된다. 불리언 회로 군 ${\displaystyle C_{0},C_{1},\dots }$이 DLOGTIME-균일하다는 것은 함수 ${\displaystyle 1^{n}\mapsto desc(C_{n})}$이 암묵적으로 DLOGTIME 계산 가능하다는 것을 의미하며, 여기서 ${\displaystyle desc(C_{n})}$은 회로의 설명이다.

이는 다음의 의미에서 매우 약하다: ${\displaystyle {\mathsf {AC}}_{0}^{0}\subsetneq {\mathsf {DLOGTIME}}\subsetneq {\mathsf {AC}}_{2}^{0}}$ (여기서 AC는 0에서 2 사이의 깊이를 갖는 DLOGTIME-균일한 무제한 팬인 회로로 구성됨). 또한 ${\displaystyle {\mathsf {DLOGTIME}}}$은 ${\displaystyle {\mathsf {AC}}_{1}^{0}}$과 비교 불가능한데, 이는 둘 중 어느 것도 다른 하나를 포함하지 않는다는 뜻이다 (XOR은 DLOGTIME에 속하고, AND와 OR은 ${\displaystyle {\mathsf {AC}}_{1}^{0}}$에 속함). DLOGTIME-균일성 가정이 중요한 이유는 그렇지 않으면 ${\displaystyle {\mathsf {AC}}_{0}^{0}}$ 회로 군조차 인덱스 선택 과정에서 계산 불가능한 시퀀스를 인코딩할 수 있기 때문이다.

${\displaystyle {\mathsf {DLOGTIME}}\subset {\mathsf {AC}}_{2}^{0}}$임을 보이기 위해, 기계가 단지 ${\displaystyle O(\log n)}$번의 임의 접근 읽기만을 수행할 수 있으며, 각각이 하나의 입력 비트를 반환한다는 점을 참고하자. 이러한 계산의 기록을 $${\displaystyle \left(\left(p_{1},b_{1}\right),\ldots ,\left(p_{c\log n},b_{c\log n}\right)\right)}$$와 같이 탐색한 위치와 관찰된 비트의 정렬된 리스트라고 하자. 각 ${\displaystyle p_{t}}$는 이전에 읽은 비트에 의해 결정되므로, 가능한 기록은 ${\displaystyle 2^{c\log n}={\mathsf {poly}}(n)}$개뿐이다. 각각의 수락 기록에 대해, "위치 ${\displaystyle p_{j}}$가 비트 ${\displaystyle \mathrm {b} _{j}}$를 포함한다"는 리터럴 ${\displaystyle \mapsto }$ ${\displaystyle c\log n}$개를 정확히 확인하는 AND 게이트를 만든다. 이 모든 게이트를 하나의 큰 OR에 연결한다. 이것이 ${\displaystyle {\mathsf {AC}}_{2}^{0}}$ 회로를 생성한다. 구성에 의해, 이 구성이 ${\displaystyle {\mathsf {DLOGTIME}}}$-균일하다는 것은 자명하다.

각주