Una domanda riguardante la definizione di tempo subesponenziale deterministico (SubExp)

Question

Prima guarda la definizione di SubExp da Zoo di complessità:

.

SubExp: (Deterministics SubExponential-Time) L'intersezione del Dtime ( $ 2 ^ {n ^ \ Epsilon} $ ) Overy $ \ Epsilon $ > 0. (Si noti che l'algoritmo utilizzato può variare con $ \ epsilon $ .) Oppure può essere scritto come: subexp= $ \ BigCap _ {\ Epsilon> 0} $ Dtime $ (2 ^ {n ^ \ \ \ \ \ \ \ \ \ \ \ \ \ Epsilon}) $ .

Quindi, porto la definizione di exp che è:

.

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

La definizione di EXP è chiara, poiché include tutto il polinomio di N alla potenza di 2. (ad es. $ 2 ^ {n ^ {30}} $ o $ 100 ^ {n ^ {99}} $ ecc.)

Prima domanda: cos'è il dominio di $ \ epsilon $ ? Immagino sia tra 0 e 1 ma non ha specificato nella definizione. È normale che quando abbiamo $ \ epsilon $ quindi significa tra 0 e 1.

Seconda domanda: ora, in caso di subexp, non è chiaro come la definizione riguarda l'intersezione? Voglio dire, non dovrebbe essere scritto come segue: $ \ bigcup_ {1> \ epsilon> 0} $ dtime $ (2 ^ {n ^ \ Epsilon}) $ . Ad esempio per definizione sopra qual'è l'intersezione di: $ 2 ^ {n ^ {0.01}} ^ Bigcap 2 ^ {n ^ {0.02}}? $ Terza domanda: ci sono due definizioni di subexp in wikipedia , è La definizione che prende il soprabito subasceniale o non lo facciamo perché questo è il motivo per cui abbiamo due definizioni.

Grazie!

Answer 1

Nella definizione di SubExp, $ \ Epsilon $ gamma su tutti i reali positivi. Ma ottieni la stessa definizione se chiedi a $ \ Epsilon <\ epsilon_0 $ , per un $ \ Epsilon_0> 0 $ di tua scelta; Se chiedi a quella $ \ Epsilon $ Sii razionale; Se vai su $ \ Epsilon= 1 / N $ ; e così via. Questo perché Dtime è monotono: se $ f \ leq G $ quindi $ \ mathsf {dtime} (f) \ semeteq \ mathsf {dtime} (g) $ .

Una definizione alternativa di SubExp sarebbe: $$ \ mathsf {subexp}=bigcup_ {g (n)= o (1)} \ mathsf {dtime} (2 ^ {n ^ {g (n)}}), $$ Spesso denotato semplicemente da $ \ mathsf {dtime} (2 ^ {n ^ {o (1)}}) $ .

Alcuni esempi: $ \ mathsf {p} \ sottomessoq \ mathsf {subexp} $ ; Una funzione che può essere calcolata in tempo $ 2 ^ {n ^ {1 / \ log \ log n}} $ è in $ \ mathsf {subexp} $ ; e una funzione che può essere calcolata in tempo $ 2 ^ {\ log ^ {10} n} $ è in $ \ mathsf {SubExp} $ .

In contrasto, una funzione che può essere calcolata in tempo $ 2 ^ {n ^ {1/10}} $ non è necessariamente in $ \ mathsf {subexp} $ (e dal teorema della gerarchia del tempo, c'è una tale funzione che è esterna $ \ mathsf {subexp} $ ).

Una funzione in $ \ mathsf {dtime} (2 ^ {n / \ log n}) $ si trova in titolare ma non necessariamente in subxp.