关于确定性子统计时间（SupExp）的定义的问题

Question

首先查看复杂性动物园的子区的定义：

子exp :(确定性区分 - 时间） dtime（ $ 2 ^ {n ^ \ epsilon} $ ）ever $ \ epsilon $ > 0。 （请注意，所使用的算法可能因 $ \ epsilon $ 。）或它可以写入：supexp= $ \ bigcap _ {\ epsilon> 0} $ dtime $（2 ^ {n ^ \ epsilon}）$ 。

所以，我带来了exp的定义，即：

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

exp的定义很清楚，因为它包括n的所有多项式到2.（例如 $ 2 ^ {n ^ {30}} $ 或 $ 100 ^ {n ^ {99}} $ 等。）

首先问题：什么是 $ \ epsilon $ 的域名？我猜它在0到1之间，但它没有在定义中指定。是通常的，当我们有 $ \ epsilon $ 然后它意味着在0到1之间。

第二个问题：现在，在子区的情况下，目前尚不清楚定义如何关于交叉点？我的意思是，不应该写下来： $ \ bigcup_ {1> \ epsilon> 0} $ dtime $（2 ^ {n \ epsilon}）$ 。例如，通过上面的定义是什么： $ 2 ^ {n {0.01}} \ bigcap 2 ^ {n ^ {0.02}}？$

第三个问题： wikipedia ，有两个分为子句那里的定义占用了所有子折叠或我们不这样做，因为这就是我们有两个定义的原因。

谢谢！

Answer 1

在Subexp的定义中， $ \ epsilon $ 范围内所有正面真实。但是如果您要求 $ \ epsilon <\ epsilon_0 $ ，则获得相同的定义，对于 $ \ epsilon_0> 0 $ 您的选择;如果您要求 $ \ epsilon $ 是合理的;如果您只换过 $ \ epsilon= 1 / n $ ;等等。这是因为dtime是单调：如果 $ f \ leq g $ 那么 $ \ mathsf {dtime}（f）\ subseteq \ mathsf {dtime}（g）$ 。

子区的替代定义是： $$ \ mathsf {supexp}=bigcup_ {g（n）= o（1）} \ mathsf {dtime}（2 ^ {n ^ {g（n）}}）， $$ 通常只是用 $ \ mathsf {dtime}表示表示（2 ^ {n ^ {o（1）}）$ 。

一些示例： $ \ mathsf {p} \ subseteq \ mathsf {subexp} $ ;可以在时间 $ 2 ^ {n ^ / log \ log n}} $ 在中$ \ mathsf {subexp} $ ;和一个可以在时间中计算的函数 $ 2 ^ {\ log ^ {10} n} $ 在 $ \ mathsf中{subexp} $ 。

相反，可以在时间 $ 2 ^ {n {1/10}} $ 不一定在 $ \ mathsf {supexp} $ （以及时间层次结构，存在这样的函数，它在 $ \ mathsf {subexp} $ ）。

在 $ \ mathsf {dtime}中的函数}（2 ^ {n / log n}）$ 在SEMEPT中呈现，但不一定在SUBEXP中。