Вопрос относительно определения детерминированного субэкспоненциального времени (подтекп)

Question

Первый посмотрите на определение подсчетов от зоопарка сложности:

SUBEXP: (детерминированное субэкспоненциальное время) Пересечение DTETTE ( $ 2 ^ {n ^ \ epsilon} $ ) по всем $ \ epsilon $ > 0 (Обратите внимание, что используемый алгоритм может варьироваться в зависимости от $ \ epsilon $ .) Или он может быть записан как: subexp= $ \ bigcap _ {\ epsilon> 0} $ dte $ (2 ^ {n ^ \ epsilon}) $ .

Итак, я приношу определение exp, которое есть:

exp= $ \ bigcup_ {k \ geq 1} $ dte $ (2 ^ {n ^ k}) $

Определение exp понятно, поскольку он включает в себя все многочлены n до мощности 2 (например, $ 2 ^ {n ^ {30}} $ или $ 100 ^ {n ^ {99}} $ etc.)

Первый вопрос: что такое домен $ \ epsilon $ ? Я думаю, это от 0 до 1, но он не указывал в определении. Это обычно, когда у нас есть $ \ epsilon $ Тогда это означает от 0 до 1.

Второй вопрос: Теперь, в случае субэкспа, неясно, как определение о пересечении? Я имею в виду, не следует писать следующим образом: $ \ bigcup_ {1> \ epsilon> 0} $ dte $ (2 ^ {n ^ \ epsilon}) $ . Например, по определению выше Что такое пересечение: $ 2 ^ {N ^ {0,01}} \ bigcap 2 ^ {n ^ {0,02}}? $

Третий вопрос: есть два определения субэксп в wikipedia , Там определение, которое захватывает все подземные и мы не поскольку именно поэтому у нас есть два определения.

Спасибо!

Answer 1

В определении подседателя, $ \ epsilon $ диапазоны на всех положительных действиях. Но вы получаете то же определение, если вы спросите, что $ \ epsilon <\ epsilon_0 $ , для $ \ epsilon_0> 0 $ по вашему выбору; Если вы спросите, что $ \ epsilon $ будет рациональным; Если вы пройдете только $ \ epsilon= 1 / n $ ; и так далее. Это связано с тем, что DTE - это монотонная: если $ f \ leq g $ Тогда $ \ mathsf {dtete} (f) \ sondestq \ mathsf {dtete} (g) $ .

Альтернативное определение субэкспа будет: $$ \ mathsf {subexp}=bigcup_ {g (n)= o (1)} \ mathsf {dtete} (2 ^ {n ^ {g (n)}}), $$ Часто обозначается просто $ \ mathsf {dte} (2 ^ {n ^ {o (1)}}) $ .

Некоторые примеры: $ \ mathsf {p} \ subsretq \ mathsf {subexp} $ ; Функция, которая может быть вычислена во времени $ 2 ^ {n ^ {1 / \ log \ log n}} $ в $ \ mathsf {subexp} $ ; И функция, которая может быть вычислена во времени $ 2 ^ {\ log ^ {10} n} $ в $ \ mathsf {Subexp} $ .

Напротив, функция, которая может быть вычислена во времени $ 2 ^ {n ^ {1/10}} $ не обязательно в $ \ mathsf {subexp} $ (и теорема по времени иерархии, существует такая функция, которая лежит за пределами $ \ mathsf {subexp} $ ).

Функция в $ \ mathsf {dte} (2 ^ {n / \ log n}) $ лежит в субые, но не обязательно в подсуд.