Una pregunta sobre la definición de tiempo subexencial determinista (subexp)

Question

Primera vistazo a la definición de subexp de la complejidad zoológico:

SUBEXP: (Hora determinista subexencial) La intersección de Dime ( $ 2 ^ {n ^ \ epsilon} $ ) sobre todo $ \ epsilon $ > 0. (Tenga en cuenta que el algoritmo utilizado puede variar con $ \ epsilon $ ). O puede ser escrito como: subexp= $ \ bigcap _ {\ epsilon> 0} $ d momento $ (2 ^ {n ^ \ epsilon}) $ .

Entonces, traigo la definición de exp que es:

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

La definición de EXP es clara, ya que incluye todo polinomio de N a la potencia de 2. (por ejemplo, $ 2 ^ {n ^ {30}} $ o $ 100 ^ {n ^ {99}} $ etc.)

Primera pregunta: ¿Qué es el dominio de $ \ epsilon $ ? Supongo que está entre 0 y 1, pero no especificó en la definición. Es habitual que cuando tengamos $ \ epsilon $ entonces significa entre 0 y 1.

Segunda pregunta: Ahora, en caso de subexpreso, no está claro cómo se trata la definición sobre la intersección? Quiero decir, no debería estar escrito de la siguiente manera: $ \ bigcup_ {1> \ epsilon> 0} $ d momento $ (2 ^ {n ^ \ epsilon}) $ . Por ejemplo, por definición por encima de lo que es la intersección de: $ 2 ^ {n ^ {0.01}} \ bigcap 2 ^ {n ^ {0.02}}? $

Tercera Pregunta: Hay dos definiciones de SubExp en wikipedia , es Definición que asume todo subexponencial o no, ya que es por eso que tenemos dos definiciones.

¡Gracias!

Answer 1

En la definición de subexp, $ \ epsilon $ rangos sobre todos los reales positivos. Pero obtiene la misma definición si le pregunta a ese $ \ epsilon <\ epsilon_0 $ , para un $ \ epsilon_0> 0 $ de su elección; Si le solicita que $ \ epsilon $ sea racional; Si solo pasa por $ \ epsilon= 1 / n $ ; y así. Esto se debe a que Dime es monótono: si $ f \ leq g $ luego $ \ mathsf {dime} (f) \ subespeteq \ mathsf {d tiempo} (g) $ .

Una definición alternativa de SubExp sería: $$ \ mathsf {subexp}=bigcup_ {g (n)= O (1)} \ mathsf {d tiempo} (2 ^ {n ^ {g (n)}}), $$ a menudo denotado simplemente por $ \ mathsf {d tiempo} (2 ^ {n ^ {O (1)}}) $ .

Algunos ejemplos: $ \ mathsf {p} \ subestexq \ mathsf {subexp} $ ; una función que se puede calcular en el tiempo $ 2 ^ {n ^ {1 / \ log \ log n}} $ está en $ \ mathsf {subexp} $ ; y una función que se puede calcular en el tiempo $ 2 ^ {\ log ^ {10} n} $ está en $ \ mathsf {Subexp} $ .

En contraste, una función que se puede calcular en el tiempo $ 2 ^ {n ^ {1/10}} $ no está necesariamente en $ \ mathsf {subexp} $ (y para el teorema de la jerarquía de tiempo, existe una función que se encuentra fuera $ \ mathsf {subexp} $ ).

Una función en $ \ mathsf {d tiempo} (2 ^ {n / \ log n}) $ se encuentra en Subep pero no necesariamente en SubExp.