準線形対本質的に線形の時間変換可能なモデルの例

Hennie-Stearnsの定理によれば、$ k ge $ 2 $を持つ$ k $
-tapeチューリングマシンは、loglinear blowup($ O(t times log {(t)}
$)で翻訳できます。

これは、loglinear
blowが構成上閉じられていないことを除いて、モデルの等価クラスを定義する。だから、もし我々が本当に離れて抽象化したいなら
チューリングマシン、我々は少なくとも準線形を考慮する必要があります ($ t times log {(t)} ^ {O(1)}
$)blowupは一時的に閉じます。

しかし、本質的に線形ブローアップ($ t ^ {1 + o(1)} $)の下では推移的閉包もあります。

どちらのクラスも、多項式時間アルゴリズムの指数と指数関数アルゴリズムの基底を保持します。

私の全体的な質問は、これらの2つのクラスの質的差異は何か、そして、より自然なもの(物理的または他の直観の観点から)は何か?

さらに具体的には、本質的に線形の時間ではあるが、準線形の時間ではない、または他の方向で、マルチテープマシンに変換可能なモデルの例は何ですか?タイムステップの定義を変更することで人工的に構築することができますが、私はより多くの洞察をもたらすものを期待しています。

私が思いついた一例は、多項式時間テストを満たすすべての$ n
$ビット文字列を数えるアルゴリズムの違いを示しています。これは、擬似線形のブローアップによって保存される$ 2 ^ n times
n ^ {O(1)} $時間で実行されるが、$ 2 ^ {n} times 2 ^ {o(n) }
$であり、これは、同じモデルで多項式時間で単一の文字列をテストすることはできますが、各ビット列を平均的にテストするために多項式以上の処理が必要であることを意味します。私は、ランダムなエラーを経験し、時間の半分以上が正しいと予想されるマシンによって説明されると想像しています。通常、正しい数を推測するためには、$
2 ^ n
$文字列のそれぞれの存在または不在を事実上確かめる必要があります。そのため、文字列ごとに多項式時間テストよりも平均的に多くの時間を費やすのです時間の右$
51 %$でなければなりません。

[編集:それは有用であるために、以下の中であまりにも多くのエラーがあると思う。私はまだ同じアイデアを開発しようとしています。それは、準線形の時間に翻訳可能な数を追跡するのが大変なマシンです。

Let me expand on that because it seems to be approaching
what I’m looking for. Suppose an error-prone machine is one such
that, with a fixed probability $p$, an attempt to change a value on
any working tape fails. If it writes the existing value back that
always works. Halting with an output means halting strictly more
than half the time with the same output, and halting within a
certain time means always halting within that time. The
latter definition means that if we write each bit by sitting in a
loop until it is correct, then the time becomes unbounded; this
lets us simulate an ordinary Turing machine, but not with any time
translation. But we can simulate an ordinary machine on the
error-prone machine up to $t$ steps by writing every bit $b(t)$
times, making its probability of being incorrect $p^{b(t)}$. There
is a $b(t) in O(log{(t)})$ sufficient to operate perfectly for
$t$ steps more than half the time, and $t times b(t)$ is only
loglinear, but for a time translation we need a universal machine
and in that situation we’re not given $t$ in advance. So what I’m
curious about now is how tightly we can constrain the time
translation factor and still be correct half the time, and whether
we can use something like this to characterize essentially linear
time translations vs. quasilinear ones.

I believe I can demonstrate that this model has a time
translation in $O(t^k)$ for every $k>1$. Dedicate a working tape
to keeping track of the number of times our universal machine is to
repeat each emulated step. It contains a string of ones delimited
by blanks at the ends. The outer loop of the universal machine
walks the list of ones from left to right, attempting to repeat the
same emulation step in between movements. When it reaches the end,
it attempts to write another one, and then resets itself by walking
back to the left end, finally advancing to the next emulation step.
This seems like more than enough repeats to be half-correct, and
we’re effectively taking $b(n) approx (1-p) times n$ resulting in
an essentially quadratic time translation. We can generalize this
by adding another counter tape to control the extension of the
first one, bringing the time translation down to
$O(t^{frac{3}{2}+o(1)})$, and repeating this gives us any
superlinear polynomial bound. Is it possible to bring this down to
quasi- or essentially linear?

ベストアンサー

私は基本的に線形v準線形の全体的な比較から始め、次に要求された計算モデルの具体例を挙げます。

等価関係として、準線形時間($ チルド{0}
$で表される)は、多数の異なる逐次決定論的モデル間で頑強な最も細かい尺度です。対照的に、本質的に線形時間は、多項式指数を保存する最も粗い一様な尺度である。

準線形時間の2つの一般的なクラス

基本的に線形の時間であっても、等価であることが知られている not
モデルの2つのよく使用されるクラスがあります。

  1. マルチテイリングチューリングマシン、2テープマシン、1テープ、スタック(忘れていても)

  2. RAMベースのマシン(メモリアクセスのコストの変動)、バイナリツリー上のチューリングマシン、

Notes:
* In both classes, the models separated by a comma are quasilinear
time equivalent.
* Most fine-grained complexity results in literature use RAM-based
machines.
* Multitape Turing machines with two-dimensional tapes appear to be
intermediate between (1) and (2).
* If our computational model is Turing machines with
multidimensional tapes (with the dimension arbitrary and dependent
on the machine), then it is equivalent to RAM-based machines under
$O(n^{1+ε})$ reducibility for every $ε>0$ (even for single tape
machines), but as far as we know, not under quasilinear or
$O(n^{1+o(1)})$ reducibility.

擬似線v本質的に線形アルゴリズム/縮小

Quasilinear時間は本質的に線形時間よりも頻繁に使用されます。なぜなら、より精密であり、余分な精度がしばしば自由になるからです。自然な半指数関数的成長率がほぼ欠如していることに関連して、実行時間はしばしば$
a ^ nn ^ {O(1)} $や$ n ^ b¥log(n)^ {O 1)} $であり、これらの場合、$ チルダ{0}(a ^
n)$と$ チルド{0}(n ^ b)$を使うことは、時間を本質的に線形因数にするよりも正確です。
(表記上の注意:一部の著者は時間$ a ^ n( log n)^ {O(1)} $に対して$ チルド{O}(a ^ n)

However, some algorithms have a more complicated run time:
– A $2^{(log n)^c}$ multiplicative factor is inverse
quasipolynomial for $0 < c < 1$, and is essentially linear
but not quasilinear. It is the most common example of such
times.
– For APSP (all pairs shortest paths) we have a more than
quasilinear speed up over $O(n^3)$ but no known $O(n^{3-ε})$
algorithm, and similarly for problems that are in a certain
specific sense reducible to APSP.
– Known CNF SAT algorithms have a more than quasilinear speed over
simple complete search time (note that formula length is polynomial
in the number of input variables and polylogarithmic in the search
time), but under a variant of SETH (Strong Exponential Time
Hypothesis) cannot have (in the worst case) more than an
essentially linear speed up. For Formula SAT, we only have a
quasilinear speed up.

具体的な例

We will use Turing machines and circuits in what may be
described as a weakly infinite-dimensional tape/space. In one
example, each point is a sequence $x_1,x_2,…$ of natural numbers
such that $x_{i+1}≤x_i/2$. Alternatively, we could have used
$x_i/k$ (rational constant $k>1$), or something else, the main
point is that it is a sufficiently efficiently computable space
whose proximity is more than polynomial but is quasipolynomial
rather than exponential. For navigating the space using a finite
internal state, we can include the movement dimension in the
external state and have a command to cycle through available
dimensions.

このような空間上の単一のヘッド/テープチューリングマシンは、通常のマルチテキストマシンやRAMベースのマシンでさえ、本質的に線形ではあるが準線形の時間ではシミュレートできません。不可能な証明は、単純な通信の複雑さの議論を使用します。このような空間上のマルチテイパーまたはマルチヘッドチューリングマシンが、通常のマルチテュラーチューリングマシン、またはRAMベースのマシン、またはその両方と同等の準線形時間であるか、または厳密には中間のパワーであるかは問わない。

このような空間における十分に均一な回路は、本質的に線形ではあるが、擬似線形ではないマルチテューブルチューリングマシンをシミュレートすることができる。ある方向では、本質的に線形サイズの増加を伴って空間内に任意の回路を埋め込むことができる。もう一つの方向は、通信の複雑さの議論によるものです。

返信を残す

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