時間階層の定理はどれほどきめ細かなモデルにできるのか?

鋭いまたは付加的な空間階層定理の1つのバージョンは、チューリングマシン(および他の多くの決定論的逐次計算モデル)のためのものである。スペース}(f)空間構成可能な$
f(n)$のスペース。

$ mathrm {Time}(f + O(1))⊊ mathrm {Time}(f + O(g))$
gのための類似した鋭いバージョンを持つ合理的な計算モデルがありますか? $ g(n)≥ log(n +
f(n))$で時間計算可能な$ f(n)$?

Since I already know one (arguably reasonable) class of models
with the sharp time hierarchy, I am including it as an answer, but
I am still interested in related results, including
– other models with the sharp time hierarchy theorem
– whether this model or other models were studied in literature
– weaker forms of time hierarchy, especially if stronger than
$mathrm{Time}(f) ⊊ mathrm{Time}((1+ε)f)$
– whether there is a speed-up theorem for Turing machines with a
fixed number of binary tapes that would prevent this form of sharp
time hierarchy.

Footnotes/References:
* The additive/sharp space hierarchy theorem can proved using
“Halting Space-Bounded Computations” by Michael Sipser (1978). See
also “Improved time and space hierarchies of one-tape off-line TMs”
by Kazuo Iwama and Chuzo Iwamoto (1998).
* A weak form of additive time hierarchy is discussed in “Computational Models with No Linear
Speedup
” by Amir Ben-Amram, Niels Christensen, Jakob Grue
Simonsen (2012).

ベストアンサー

対角化に基づく時間階層定理の3つの要素は、普遍的なシミュレーション、タイミング、および反転である。これらの操作が効率的である計算モデルを選択する(または定義する)ことによって、我々は鋭い階層定理を得る。特に、一定の条件を満たす時限仮想化プリミティブを持つモデルを使用することによって、要求された形式で時間階層が得られます。しかし、鮮明な空間階層とは異なり、正確な時間の使用と階層はモデルごとに(したがっていくらか任意に)基づいています。

If we set up things appropriately, the following algorithm can
be implemented in time $f(n)+O(g(n))$ but not in time
i.o.-$(f(n)+O(1))$ where $g(n)≥log(n+f(n))$ and $f$ is $g$-time
computable (i.o. means infinitely often):
* Determine the input length $n$, and compute $f(n)$.
* Read a small portion of the input to get a code $M$.
* Run TimedVirtualize($M$, $f(n) + lg(n)$)  # check whether
$M$ accepts the input in $f(n) + lg(n)$ steps; TimedVirtualize
must be fast enough.
* If $M$ accepts, then Reject, and otherwise Accept.

時間階層の場合、最も簡単なモデルは、パラメータを書き込むための特別なテープと、{Accept、Reject、Timeout}→{Accept、Reject、Timeout}のマッピングでTimedVirtualizeを呼び出す命令を持つことです。
TimedVirtualizeは終了し、TimedVirtualizeはリアルタイムで実行されます)。

ただし、仮想化を繰り返し使用することは当然のことですが、残りの回答では、時限仮想化モデルのクラスの一部の仕様と、そのモデルを効率的に実装する方法について説明します。

タイムド仮想化

計算モデルは、プログラムの解釈方法とそれにかかる時間を定義します。問題は、$ n
$が入力長であるすべての有効な入力に対して、あるプログラムが時間的に$ f(n)$を解く場合、時間$ f
$で解ける。入力の長さは対数時間で決定できると仮定します。

One approach to timed virtualization is to use code, data, and
privileged data ‘tapes’. The code tape need not be directly
accessible. The data and privileged data tapes are accessible,
except that at a given time, a portion of the privileged data tape
may be invisible and undetectable. In addition to ordinary
instructions, the models have a virtualization function
TimedVirtualize(Code, Time) such that:

  1. マシンは、コードをタイムステップまで実行します(コードと時間は特権データテープから取得されます)。コードが実行され、Code(コード)とデータテープを現在の状態に初期設定したかのように、各ステップがカウントされます。すべての命令(TimedVirtualizeを含む)は許可されます。コードは、特権データテープが最初は空であるとみなします。以前の特権データは変更されません(ただし、階層の定理は消去されても保持されます)。

  2. TimedVirtualizeは、コードがタイムアウトしたか、受け入れ/拒否命令が呼び出されたかによってタイムアウト/受け入れ/拒否をコード化した値を返します。

  3. (オプションの拡張子)
    TimedVirtualize(Code、Time)のステップ数は、コードが取ったステップ数(≤Time)と時間に依存しないオーバーヘッドを足したものになります。

  4. フルスピード条件:</$ O( log( mathrm
    {Time}))$。

  5. TimedVirtualizeにはいくつかの機能を追加できますが、階層定理には必要ありません。たとえば、初期特権データの設定、コードの所要時間の取得、無制限時間の許可、またはオプションでコードと(可視)特権データを置き換える(つまりスペースを節約する)非仮想化実行を行うことができます。

コードとタイミングに関する基本的な仮定の下で、このタイプのすべてのモデルは、鋭い時間階層の定理を満たす。 $
f(n)$の計算は、最後にワークテープを消去する必要があります(読み込み専用入力テープを使用しない場合は入力データを除く)。消去を含めるために時間構成性を定義するか、消去が線形時間で実行できるモデルを使用することができます。

効率的な例と実装

すべての$ k $に対して、線形時間$ k $
-tapeチューリングマシン(時間はシミュレートされたマシンに依存します)でシミュレートできるモデルがあり、$ k + 2 $ -
テープのチューリングマシンであり、フルスピードの条件が計算上合理的であることを示唆しています。
(モデルタイミングを定義するので、実装は合理性の重要な証拠です。)2つのテープギャップを0に減らすことができるかどうかはわかりません。

このようなモデルを得るために、コードの解釈とタイミングを修正し、効率的なユニバーサルチューリングマシンがコードサイズから独立した一定の係数で、線形時間でコードをシミュレートできるようにします。たとえば、コードをチューリングマシンと解釈することはできますが、相対的なオフセット$
d $(ビット単位)と$ k(d +
1)$時間の指定と、TimedVirtualizeの規則とタイミングまた、ランダムアクセステープがなければ、頭/カーソルの位置が重要であることに注意してください)。モデルのテープに加えて、マシンはタイマーを格納するテープを使用します(実装されている場合は、スペースの境界)。時間$
t $には$ O(t/ log
t)$のタイマーがあるかもしれませんが、アンチモニノニックのケース(後にトリガーされるタイマーが遅くトリガーされる)が必要なだけなので、最も内側のタイマーにカウンタを使用できます。
TimedVirtualizeが終了したら、減算を使用して前のタイマーを更新します。

タイムスペース階層

私たちが妥当な方法で空間の使用を定義し(そして仮想化で空間の境界を許すならば)、TimeSpaceの鋭い理論定理を持つモデルを得ることさえできます:$
mathrm {TimeSpace}(T + O(1)、S + O $ mathrm {TimeSpace}(g、h)$ -
コンストラクタブル$(T、S)$を使って$ mathrm {TimeSpace}(T + O(g)、S + h + O $
g(n)≥ log(n)$と$
T(n)≥n$である。正確なタイミングの必要性は、(少なくとも現在階層を証明できる範囲で)スペース階層をここではあまり鮮明にしません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です