細かい指数関数の複雑さクラスの最も一般的な設定?

$ 2 $ -tapeチューリングマシンでtime $(b + o(1))^ n = 2 ^ { log_2 {(b)}
times n + o(n)} $で計算可能な関数のクラスを考えてみましょう。

Hennie-Stearnsの定理によって、同じ関数は、任意の$ k geq 2 $に対する$ k $
-tapeチューリングマシンで、時間$(b + o(1))^ n $で計算可能です。そして、この等価性を、$ 2 $ –
テープ・マシンとの間で本質的に直線的な時間変換を有する任意の計算モデルに拡張することができる。しかし、これは非常に自然な階級ではなく、たとえ拡張された教会
– チューリング論文を信じているとしても。

空間の使用量も考慮すると、より多くのモデルは、$ O(t times s ^
k)$という形の時間の翻訳が可能です。たとえば、$ 2 $のテープ・マシンを$ 1
$のテープ・マシンでエミュレートする場合、各時間ステップで使用されるスペースをスキャンするだけで済みます。したがって、時間の爆発は$
O(t times s)$です。同様に、RAMモデルの場合、小さな$ k
$が働いているようです。連想メモリとして1つのテープを使用し、別のテープに書き込まれたキーを見つけるためにキーと値のペアのリストを使用します。

今度は、$ F $は$(b + o(1))^ n $時間と$ 2 ^ {o(n)} =(1 + o(1))^ n
$で計算可能です。スペース。私は明らかなものがすべて働いているので、私が使っているモデルを言う必要はありません。ここではトレードオフのようなものがあります。サブ指数的なスペース制限と引き換えに、大きな文脈では不変である関数の時間複雑さに対して特定の基底$
b $を指定できます。

それは私が今この問題を理解している限りです。そして、私は何かについて完全に間違っている可能性があるので、私は上記のことが大体正しいという安心感を部分的に探しています。しかし、それはすべてそれにあるのだろうか?関数の指数関数時間基底を一意に指定できる他の一連の仮定がありますか?

例:ルビンスタインの定理では、ベース$ 2 ^ frac {1} {3}
$で因数分解することができます。アルゴリズムは準指数空間を使用するため、この結果はモデル全体で堅牢です。

例:素数を見つけるための平方根障壁。チューリングマシン上で指数関数的なスペースを必要とするアルゴリズムを提示することで壊れてしまったのであれば、それは本当に自然な結果になるのでしょうか、あるいは単に機械モデルの人工物でしょうか?

例:強い指数時間仮説。 RAMプログラムは、$ 2 $以下の基底で一般的な$ text {CNF-SAT}
$を指数関数的時間で解くことができますが、指数空間も必要とするかもしれませんので、TMに変換されたときにアルゴリズムは指数少なくとも$
2
$の基礎を持つ時間と(少し弱められた)SETHはTMモデルでのみ真ですか?より多くのモデルに適用可能にするためにサブ指数空間アルゴリズムのみが考慮されるSETHの変種がありますか?あるいは、私はこの仮定なしに一般性が失われていないということを理解していない何らかの理由がありますか?

ベストアンサー

あなたの説明は正しいように見えます。 $ t ^ {o(1)} $空間を使用するアルゴリズム(入力サイズが$ t ^
{o(1)} $であるか、入力に対してランダムアクセスがある場合の決定論的モデル(本質的に線形時間変換の下で)
)は素晴らしい見解です。 (ただし、ランダム化されたアルゴリズムが($ t ^ {1(1)}
$入力サイズであっても)高速であるかどうかはまだ分かっており、量子アルゴリズムはより高速であり、教会テューリングの延長論に違反する可能性もあります。

本質的に直線的な翻訳の2つの他の場合:

    $ t ^ {1 + o(1)} $ sizeと$ t ^ {o(1)} $
    depthを持つ妥当なパラレルモデルは同等であると見なされます(変換にはまだ$ t ^ $ t ^ {1 + o(1)} $時間と$
    t ^ {o(1)} $深さ)/li>

  • 非決定論的なチューリングマシンは、非決定論的なRAMマシンの履歴を推測し、

素数を求めるための平方根の障壁は、計算上の問題ではなく、数論の問題である可能性が高い。 $ x
$以上の最小の素数を見つけるための純粋なアルゴリズム(多項式時間素数検定付き)は、多項式時間($ log x
$)であると推定されます。 RAMを使用してTMを使わずに時間$ O(10 ^ {k/2-ε})$に小数点の$ k
$の素数を見つけ出す証明可能な決定論的アルゴリズムは、質問に答えることができないメモリ集中型部分乱数化連続する素数の間の$ O(n ^
{1/2-ε})$の上限。

SETHの場合、規則はRAMマシンを使用することです。さもなければ、その重要なアプリケーション、細かい複雑さの下限は、RAMマシンでは機能しません。それは、SETH⇒
“TMHのためのSETH”⇒ “$ 2 ^ {o(n)} $
space”のSETHのいずれかが逆になる可能性があるかどうかは分かりません。

また、SETHの下では、いくつかの問題に対して、最良の指数はTMとRAMで同じです。例えば、最小の編集距離については、本質的に2次の時間アルゴリズムをTMに対して働かせることができ、i.o.本質的に2次の下限はRAMの場合でも有効です。

返信を残す

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