Aceleração não determinística da computação determinística

O não-determinismo pode acelerar a computação determinística? Se sim, quanto?

Ao acelerar a computação determinística por não-determinismo, quero dizer resultados da forma:

$\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n)$

Por exemplo, algo como

$\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

Qual é o resultado da aceleração mais conhecido da computação determinística por não-determinismo? E quanto a ou mesmo no lugar de ?$\mathsf{\Sigma^P_kTime}(n)$$\mathsf{ATime}(n)$$\mathsf{NTime}(n)$

Suponha que as classes de complexidade sejam definidas usando máquinas de Turing de fita múltipla para evitar as peculiaridades conhecidas das máquinas de Turing de fita única de tempo sub-quadrático.

Você não deve esperar uma aceleração emocionante. Nós temos

e a simulação mais conhecida do tempo determinístico pelo espaço ainda é o teorema de Hopcroft – Paul – Valiant

Assim, não se sabe que o não determinismo ou a alternância aceleram mais do que um fator logarítmico. (Eu suspeito que nenhuma aceleração super-linear também seja conhecida, embora não tenha certeza se o teorema do HPV não pode funcionar com o ATIME no lugar do DSPACE.)

Existem dois conceitos distintos:

(1) Simulação eficiente de máquinas determinísticas por máquinas não determinísticas.

(2) Acelere os resultados obtidos aplicando uma simulação repetidamente.

Não conheço nenhuma simulação eficiente de máquinas determinísticas por não determinísticas, mas conheço vários resultados de aceleração que poderiam ser usados ​​se existirem simulações eficientes.

Considere a classe de idiomas que são decidíveis por uma máquina de Turing não determinística em execução por t ( n ) tempo usando apenas g ( n ) suposições não determinísticas. Em outras palavras, o comprimento da testemunha é limitado por g ( n ) .$NTIGU(t(n), g(n))$$t(n)$$g(n)$$g(n)$

Se você tem uma simulação mais eficiente usando apenas suposições não determinísticas de , acredito que você pode acelerar um pouco. Em particular, acredito que você pode provar o seguinte:$\log(n)$

Se , então D T I M E ( 2 $DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$.$DTIME(2^{\sqrt{n}}) \subseteq NTIME(n)$

Se você achar isso interessante, eu posso escrever a prova.

Ryan Williams introduziu algumas acelerações relacionadas em "Melhorar a pesquisa exaustiva implica limites inferiores superpolinomiais".

Aqui está uma explicação para o porquê de uma aceleração não-determinística geral do cálculo determinístico, mesmo se verdadeira, seria difícil de provar:

Suponha que seja mantida uma aceleração não determinística quadrática geral da computação determinística como . Por uma questão de contradição, assuma que S A T ∈ D T i m e ( o ( n 2 / lg n ) ) . Há uma redução no tempo quadrático de qualquer problema em N T i m e ( $\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n)$$\mathsf{SAT} \in \mathsf{DTime}(o(n^2/\lg n))$ Para S A T . Combinando-os, teríamos D T i / lg n ) ) contradizendo o teorema da hierarquia de tempo.$\mathsf{NTime}(n)$$\mathsf{SAT}$$\mathsf{DTime}(n^4) \subseteq \mathsf{DTime}(o(n^4/\lg n))$

Portanto, uma aceleração não terminística geral quântica do cálculo determinístico implicaria um limite inferior para :$\mathsf{SAT}$

.$\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n) \to \mathsf{SAT} \notin \mathsf{DTime}(o(n^2/\lg n))$

Portanto provando uma velocidade quadrática-se não-determinístico geral de computação determinista é, pelo menos, tão forte quanto a revelar inferior limites quase quadráticas em .$\mathsf{SAT}$

Da mesma forma, para qualquer função com bom comportamento :$f(n)$

.$\mathsf{DTime}(f(n^2)) \subseteq \mathsf{NTime}(n) \to \mathsf{SAT} \notin \mathsf{DTime}(o(f(n)/\lg n))$

(Se no lugar de escolhermos um problema difícil para N T i m e ( n ) sob reduções de tempo linear, isso daria f ( n ) / lg n um limite inferior para esse problema. Se o número de fitas da máquina for de k ≥ 2 , podemos usar o teorema da hierarquia de tempo de Fürer, que não possui o fator lg n .)$\mathsf{SAT}$$\mathsf{NTime}(n)$$f(n)/\lg n$$k\geq 2$$\lg n$