Une question concernant la définition du temps subexponentiel déterministe (subexp)

Question

Premier regard sur la définition de subexp de la complexité zoo:

subexp: (Temps de sousexponentiel déterministe) L'intersection de DTNE ( $ 2 ^ {N ^ \ EPSILON} $ ) sur tout $ \ epsilon $ > 0. (Notez que l'algorithme utilisé peut varier avec $ \ epsilon $ .) Ou il peut être écrit comme suit: subexp= $ \ BigCap _ {\ epsilon> 0} $ DTNE $ (2 ^ {N ^ \ EPSILON}) $

Alors, j'apporte la définition d'exp, ce qui est:

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

La définition de l'exp est claire, car elle inclut tout le polynôme de N à la puissance de 2. (par exemple, 2 ^ {n ^ {30}} $ ou 100 $ ^ {n ^ {99}} $ etc.)

première question: quel est le domaine de $ \ epsilon $ ? Je suppose que c'est entre 0 et 1 mais cela n'a pas spécifié dans la définition. Est-il habituel que lorsque nous avons $ \ epsilon $ alors cela signifie entre 0 et 1.

Deuxième question: Maintenant, en cas de subexp, il n'est pas clair comment la définition concerne l'intersection? Je veux dire, ne devrait pas être écrit comme suit: $ \ bIGCUP_ {1> \ epsilon> 0} $ DTNE < Conteneur mathématique "> $ (2 ^ {n ^ \ epsilon}) $ . Par exemple, par définition ci-dessus, quelle est l'intersection de: 2 ^ {n ^ {0.01}} \ bigcap 2 ^ {n ^ {0.02}}? $

Troisième question: Il y a deux définitions de subexp dans Wikipedia , est Il y a une définition qui prenne la surveillance de toutes les subexponentielles ou nous ne le faisons pas, pourquoi nous avons deux définitions.

Merci!

Answer 1

Dans la définition de subexp, $ \ epsilon $ gammes sur tous les réels positifs. Mais vous obtenez la même définition si vous demandez à ce que $ \ epsilon <\ epsilon_0 $ , pour une $ \ epsilon_0> 0 $ 0 $ de votre choix; Si vous demandez que $ \ EPSILON $ Soyez rationnel; Si vous ne passez que sur $ \ epsilon= 1 / n $ ; etc. C'est parce que Dtime est monotone: si $ f \ leq g $ alors $ \ mathsf {DTNE} (F) \ Subreteq \ mathsf {dtime} (g) $ .

Une définition alternative du subexp serait: $$ \ mathsf {subexp}=bigcup_ {g (n)= O (1)} \ mathsf {DTNE} (2 ^ {n ^ {g (n)}}), $$ souvent désigné simplement par $ \ mathsf {dtime} (2 ^ {n ^ {o (1)}}) $ .

.

Quelques exemples: $ \ mathsf {p} \ sous-fichierq \ mathsf {subexp} $ ; une fonction qui peut être calculée dans le temps 2 ^ {n ^ {1 / \ journal \ journal n}} $ est dans $ \ mathsf {subexp} $ ; et une fonction qui peut être calculée dans le temps 2 ^ {\ journal ^ {10} n} $ est dans $ \ mathsf {Subexp} $ .

En revanche, une fonction qui peut être calculée dans le temps 2 ^ {n ^ {1/10}} $ n'est pas nécessairement dans $ \ mathsf {subexp} $ (et par le théorème hiérarchique temporel, il existe une telle fonction qui se trouve à l'extérieur de $ \ mathsf {subexp} $ ).

une fonction dans $ \ mathsf {dtime} (2 ^ {n / \ journal n}) $ est sous réserve mais pas nécessairement dans subexp.