NSPACEの不均一な下限

私が間違っていないと、$ E ^ {NP} subseteq { rm SIZE}(n)$ ここで、$ E ^ {NP}
$は、時間$ 2 ^ {O(n)} $で働くTMに解決可能な問題のクラスであり、サイズ$ 2 ^ {O(n)} $のNPをNP
oracle、$ { rm SIZE(n)} $はサイズ$ O(n)$の非一様な回路で解ける関数のクラスです。

上記の観察は、$ { rm NSPACE} [n] subseteq { rm SIZE} [n]
$開いている。

質問:

  1. 最小関数$ f(n)$は既知であるため 無条件に$ { rm NSPACE} [f(n)] nsubseteq {
    rm SIZE} [n] $?
  2. $ mathcal {C} nsubseteq SIZE [n] $という無条件で知られているように、$ E ^
    {NP} $を含む最小クラス$ mathcal {C} $は何ですか?
  3. 均一クラスと非均一クラスの関係の良い参考資料は何ですか?
ベストアンサー

  1. $ f(n)= omega(n)$のような任意の空間構成可能な関数$ f $に対して$ mathrm
    {NSPACE}(f(n) log n) nsubseteq mathrm {SIZE
    }(n)$。これは単純な無差別な力によって行われます:あなたは述語を計算することができます

$ は、$ O( log f(n))$の変数のブール関数の真理値表$ t $を$ 、$ C $は$ t
$を計算しません)、($ forallall $ truth-tables $ t ‘$辞書的に$ t $より小さい$ は、$
O(f(n))$ $ t ‘$)と$ t(x)= 1 $

スペース$ O(f(n) log n)$と$ O(1)$ alternationsを持つ交互のTM上の$ mathrm
{NSPACE} Immerman-Szelepcsényi定理によって、(O(f(n) log n))$となる。 ($ log
n $因子は、サイズ$ f(n)$の回路の記述が$ O(f(n) log f(n))$ビットを取り、 n) le n ^ 2
$となるので、$ log f(n)= O( log n)$となる。

  1. 同じ種類の引数は、関数$ f(n)に対して$ mathrm {TIME}(n ^ {f(n)} ^ mathrm
    {NP} nsubseteq mathrm {SIZE}
    )$を上回っています。しかし、これは本当に不幸です。例えば、固定された$ k $に対して、忘れる$ S_2 ^ mathrm
    P $も$ mathrm {SIZE}(n)$(または$ mathrm {SIZE}(n ^ k)$)
    )、それは多項式時間階層ではかなり低いので、$ mathrm {E ^ {NP}}
    $よりもはるかに小さいクラスになります。

返信を残す

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