決定論的なサブエクスポンシャルタイムの定義に関する質問（SUBEXP）

Question

複雑さZooからのSUBEXPの定義を最初に見てください：

subexp :(決定論的なsubponepentic-time） すべての $ \ epsilon $ > $ \ epsilon $ >の交差点（ $ 2 ^ {n ^ \ epsilon} $ 0。 （使用されるアルゴリズムは $ \ epsilon $ によって異なります）またはそれは次のように書くことができます.subexp= $ \ bigcap _ {¥epsilon> 0} $ dtime $（2 ^ {n ^ \ epsilon}）$

だから、私はexpの定義を持っています：

exp= $ \ bigcup_ {k \ geq 1} $ dtime $（2 ^ {n ^ k}）$

Expの定義は、2の電力に対するすべての多項式を含むので（例： $ 2 ^ {n ^ {30}} $ または $ 100 ^ {n ^ {99}} $ など）

最初の質問： $ \ epsilon $ のドメインとは0から1の間であるが、定義では指定されていませんでした。 $¥epsilon $ がある場合は、0から1の間で1となります。

2番目の質問：現在、SUBEXPの場合は、定義が交差点に関するものですか？つまり、次のように書かれてはいけません。 $ \ bigcup_ {1> \ epsilon> 0} $ dtime $（2 ^ {n ^ \ epsilon}）$ 。たとえば、次のような定義によって： $ 2 ^ {n ^ {0.01}} \ bigcap 2 ^ {n ^ {0.02}}？$

第3質問： wikipedia 、2つのsubexpの定義があります。これが2つの定義を持っている理由なので、すべてのサブファイルを引き継ぐ定義がありません。

ありがとうございました！

Answer 1

Subexpの定義では、 $ \ epsilon $ の範囲は、すべての前向きな実数に渡っています。しかし、 $ \ epsilon <\ epsilon_0 $ 、 $¥epsilon_0> 0 $を尋ねる場合は、同じ定義が得られます。あなたの選択の $ \ epsilon $ を尋ねる場合 $ \ epsilon= 1 / n $ を越えて進む場合等々。これは、dtimeがモノトーンであるためです。 $ f \ leq g $ の場合、 $ \ mathsf {dtime}（f）\ subeteq \ mathsf {dtime}（g）$ 。

Subexpの代替定義は次のようになります。 $$ \ mathsf {subexp}=bigcup_ {g（n）= o（1）} \ mathsf {dtime}（2 ^ {n ^ {g（n）}}） $$ 単に $ \ mathsf {dtime}（2 ^ {n ^ {o（1）}）$ 。

例： $ \ mathsf {p} \ subseteq \ mathsf {subexp} $ 。 $ 2 ^ {n ^ {1 / \ log \ log n}}}}}} $ は; $ 2 ^ {\ log ^ {10} n} $ には、 $ \ mathsfにある関数とその関数{subexp} $ 。

対照的に、時間 $ 2 ^ {n ^ {1/10}} $ が必ずしも $ \ mathsf {subexp} $ （そしてTime階層定理では、 $ \ mathsf {subexp} $ ）

$ \ mathsf {dtime}の関数（2 ^ {n / \ log n}）$ は、必ずしもsubexpです。