Uma pergunta sobre a definição de tempo subexponencial determinístico (subexp)

Question

Primeiro olhar para a definição de subexp do zoológico de complexidade:

.

subexp: (determinação do tempo subexponencial) A interseção de DTIME ( $ 2 ^ {n ^ \ epsilon} $ ) ao longo de todo o $ \ epsilon $ > 0. (Note-se que o algoritmo usado pode variar com a $ \ epsilon $ .) Ou pode ser escrita como: SUBEXP= $ \ bigcap _ {\ epsilon> 0} $ DTIME $ (2 ^ {n ^ \ epsilon}) $ .

Então, trago a definição de exp que é:

.

EXP= $ \ bigcup_ {k \ geq 1} $ DTIME $ (2 ^ {n ^ k}) $

A definição de EXP é clara, uma vez que inclui todas polinômio de n à potência de 2. (por exemplo, $ 2 ^ {n ^ {30}} $ ou $ 100 ^ {n ^ {99}} $ etc.)

primeira pergunta: o que é o domínio da $ \ epsilon $ ? Eu acho que é entre 0 e 1, mas não especificou na definição. É normal que, quando temos $ \ epsilon $ , então isso significa entre 0 e 1.

segunda pergunta: agora, em caso de subexp, não é claro como a definição é sobre a interseção? Quer dizer, não deve ser escrito da seguinte forma: $ \ bigcup_ {1> \ epsilon> 0} $ DTIME $ (2 ^ {n ^ \ epsilon}) $ . Por exemplo, por definição, acima do que é a interseção de: $ 2 ^ {n ^ {0,01}} \ bigcap 2 ^ {n ^ {0,02}} $

Terceira pergunta: Há dois definição de SUBEXP em wikipedia , Is Há definição que assumir todos os subexponentes ou não, porque é por isso que temos duas definições.

Obrigado!

Answer 1

Na definição de subexp, $ \ epsilon $ varia sobre todos os reais positivos. Mas você obtém a mesma definição se você perguntar a essa $ \ epsilon <\ epsilon_0 $ , para uma $ \ epsilon_0> 0 $ de sua escolha; Se você perguntar a essa $ \ epsilon $ ser racional; Se você só passar por cima $ \ epsilon= 1 / n $ ; e assim por diante. Isso é porque o Dime é monotono: se $ f \ leq g $ então $ \ mathsf {dtime} (f) \ subseteq \ mathsf {dtime} (g) $ .

Uma definição alternativa de subexp seria: $$ \ mathsf {subexp}=bigcock_ {g (n)= o (1)} \ mathsf {dtime} (2 ^ {n ^ {g (n)}}), $$ muitas vezes denotado simplesmente por $ \ mathsf {dtime} (2 ^ {n ^ {O (1)}}) $ .

Alguns exemplos: $ \ mathsf {p} \ subseteq \ mathsf {subexp} $ ; Uma função que pode ser computada no tempo $ 2 ^ {n ^ {1 / \ log \ log n}} $ está na $ \ mathsf {subexp} $ ; e uma função que pode ser computada no tempo $ 2 ^ {\ log ^ {10} n} $ está na $ \ mathsf {Subexp} $ .

Em contraste, uma função que pode ser computada no tempo $ 2 ^ {n ^ {1/10}} $ não é necessariamente na matemática $ \ Mathsf {subexp} $ (e pelo Time Hierarquia Teorema, há tal função que está fora da classe $ \ mathsf {subexp} $ ).

uma função em $ \ mathsf {dtime} (2 ^ {n / \ log n}) $ mentiras no subext mas não necessariamente no subexp.