DLOGTIME

計算複雑性理論において、DLOGTIMEは、決定論的チューリングマシン上で対数量の計算時間で解けるすべての計算問題の複雑性クラスです。入力テープがマシンがアクセスできるセルの範囲よりも長くなるため、ランダムアクセスチューリングマシン上で定義する必要があります。これは時間複雑性の非常に弱いモデルです。決定論的な時間制限がこれより小さいランダムアクセスチューリングマシンでは、入力全体にアクセスすることはできません。^{[ 1 ]}

DLOGTIMEマシンはそのまま使用されることは稀です。むしろ、通常は還元可能性を研究するための理論的構成要素の一部として使用されます。対数長を超える出力を生成するために使用することはできません。しかし、次のような意味で、間接的にそのような出力を生成するために使用できます。任意の対数長のバイナリアドレスが与えられると、対応する出力ビットが生成されます。多項式サイズの整数は対数長のバイナリ表現を持つため、DLOGTIMEではこれが可能です。

次のテープを持つ決定性チューリングマシンを考えます。^{[ 1 ] : 140}

• 読み取り専用の入力テープ。
• 読み書き可能なアドレステープ。
• 読み書き可能な作業用テープ。

この機械は、入力テープから読み取る際に、以下の手順のみが許可されます。まず「読み取り」状態に遷移し、次のタイムステップで、アドレステープ上のバイナリアドレスに従って、入力テープ上の指定されたインデックスにあるビットを受信します。

DLOGTIME は、そのような機械によって解決可能な決定問題のクラスです。${\displaystyle O(\log n)}$時間${\displaystyle 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 が計算可能であるのは、次の条件を満たす場合のみです: ^{[ 1 ] : 140}

• 多項式で制限される：ある${\displaystyle c>0}$そのため${\displaystyle f(x)\leq |x|^{c}}$すべての人々のために${\displaystyle x\in 2^{*}}$。
• ${\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-uniform である場合、${\displaystyle 1^{n}\mapsto desc(C_{n})}$は暗黙的に DLOGTIME 計算可能であり、${\displaystyle desc(C_{n})}$これは回路の説明です。^{[ 1 ] [ 2 ]}

それは以下の意味で非常に弱い。${\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}}$^{[ 1 ]} DLOGTIME の均一性の仮定は重要です。そうでなければ、$\displaystyle {\mathsf {AC}}_{0}^{0}}$回路ファミリーは、インデックスの選択において、計算不可能なシーケンスを符号化する可能性がある。

表示する${\displaystyle {\mathsf {DLOGTIME}}\subset {\mathsf {AC}}_{2}^{0}}$機械は、${\displaystyle O(\log n)}$ランダムアクセス読み取りは、それぞれ1ビットの入力値を返す。このような計算の記録を順序付きリストと呼ぶ。$${\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)}$可能な転写。受け入れる転写ごとに、これらの転写を正確にチェックするANDゲートを作成します。${\displaystyle c\log n}$リテラル${\displaystyle \mapsto }$"位置${\displaystyle p_{j}}$ビットを含む${\displaystyle \mathrm {b} _{j}}$「. これらのゲートをすべて 1 つの大きな OR に接続します。$\displaystyle {\mathsf {AC}}_{2}^{0}}$回路。この構成は、明らかに、${\displaystyle {\mathsf {DLOGTIME}}}$-均一。