Grandes lacunas entre a RAM e a complexidade da máquina de Turing

Se considerarmos apenas os problemas em P, existem grandes lacunas entre o algoritmo de RAM de palavras mais rápido e o algoritmo de máquina de Turing mais rápido para problemas específicos? Estou particularmente interessado se existem grandes lacunas para problemas naturais de interesse geral.

Sabe-se que qualquer problema que você possa calcular em uma máquina de RAM no tempo , poderá fazê-lo em uma máquina de Turing no tempo no máximo T ( n ) 2 . Você precisa observar que o tamanho total da memória usada não pode ser maior que T ( n ) , pois isso significaria que você executou mais operações de gravação que T ( n ) ; portanto, toda vez que você busca algo da memória RAM, o Turing máquina levaria no pior caso T ( n $T(n)$$T(n)^2$$T(n)$$T(n)$$T(n)$tempo para encontrar o elemento desejado sequencialmente na fita. Além do acesso à memória, o restante das operações deve demorar aproximadamente o mesmo tempo. E assim você recebe o limite.

O exemplo abaixo prova que um algoritmo que leva O ( n log ( n ) ) para resolver um problema na palavra Ram pode precisar de O ( n 2 log ( n ) 3 ) em uma Turing Machine (TM) de 1 fita que executa exatamente todos os cálculos indicados por um . Entendo que a pergunta está relacionada à 1-tape TM e só uso esta na minha resposta. Esta é uma edição para abordar as observações de Emil Jeřábek.$A$$O(n\log(n))$$O(n^2 \log(n)^3)$$A$

Encontraremos a seguinte conclusão mais geral . Para provar que a TM pode resolver em um problema resolvido em O ( T ( n ) ) por um algoritmo A na RAM, não basta executar A na TM. Um algoritmo inteligente pode ser necessário. O mesmo se aplica se alguém quiser provar um O ( n log ( n ) $O(T(n)^2)$$O(T(n))$$A$$A$$O(n\log(n))$a sobrecarga. Provar a existência de um algoritmo inteligente sempre que necessário parece longe de ser imediato, para dizer o mínimo. Isso não está de acordo com outras respostas que basicamente apenas propõem simular / executar na TM todos os cálculos de RAM (do algoritmo ) para anunciar uma complexidade de TM como O ( T ( n ) 2 ) ou O ( T ( n ) n log ( n ) ) .$A$$O(T(n)^2)$$O(T(n)n\log(n))$

Problema: Recebemos uma matriz / tabela com n = 2 k números inteiros, cada um armazenado em bits de log ( n ) . Nos é dada uma segunda matriz d com posições de log ( n ) , cada uma registrando um número de bits de log ( n ) . Para qualquer t ∈ [ 0 .. log ( n ) - 1 ] , definimos X t = 1 se a tab [ i $\texttt{tab}$$n=2k$$\log(n)$$\texttt{d}$$\log(n)$$\log(n)$$t\in[0..\log(n)-1]$$X_t=1$$\texttt{tab}[i]$MOD MOD d [ t ] ∀ i ∈ [ 0 .. n / 2 - 1 ] . Caso contrário, X t = 0 . Saída ∑ log ( n ) - 1 t = 0 X t . Considero que a entrada é dada como uma fita com n log ( n ) $\texttt{d}[t]=\texttt{tab}[n/2+i]$$\texttt{d}[t]~\forall i\in [0..n/2-1]$$X_t=0$$\sum_{t=0}^{\log(n)-1} X_t$ dígitos binários, para endereçar os comentários de Emil Jeřábek.$n\log(n)+\log(n)\log(n)$

Algoritmo na RAM$A$ Uma RAM com tamanho de palavra precisa de O ( n log ( n ) + log ( n ) 2 ) = O ( n log ( n ) ) para ler os dados de entrada da string binária. Mas depois de ler os dados, ele pode funcionar apenas com palavras do tamanho do log ( n ) . O algoritmo A calcula qualquer X t em O ( $w=\log(n)$$O(n\log(n)+\log(n)^2)$$O(n\log(n))$$\log(n)$$A$$X_t$ passando por todo i ∈ [ 0 .. n / 2 - 1 ] e testando a condição. O loop principal de A éFOR t = 0 , 1 , 2 , … log ( n ) - 1 : calcula X t . A complexidade total é O ( n log ( n ) ) (leitura de dados) + O ( n log ( n ) $O(n)$$i\in [0..n/2-1]$$A$$t=0, 1, 2, \dots \log(n)-1$$X_t$$O(n\log(n))$$O(n\log(n))$(fazendo os cálculos), para que possa fazer tudo em O ( n log ( n ) ) na RAM.$A$$O(n\log(n))$

Algoritmo na TM com 1 fita:$A$ Argumento que a TM com uma fita precisa de tempo para um t fixo . Do ponto de vista da TM, a determinação Um t é equivalente a testar a igualdade das duas cadeias binárias de comprimento ó ( n log ( n ) ) . Por exemplo, a guia de operação MOD [ i ] MOD d [ t ] pode ser equivalente a remover o bit 0 da $O(n^2 \log(n)^2)$$t$$A_t$$O(n\log(n))$$\texttt{tab}[i]$$\texttt{d}[t]$$0$ . Em tais casos, a determinação Um t é equivalente ao teste de igualdade em cadeias de bits com um comprimento n ( log ( n ) - 1 ) / 2 . É sabido que testar a igualdade de duas seqüências de comprimento m requer O ( m 2 ) na 1-tape TM, mas não consigo realmente encontrar uma referência no momento. No entanto, forneço uma prova no ps. Se a TM executar oloop principalde A , precisará gastar pelo menos O ( ( n log $\texttt{tab}[i]$$A_t$$n(\log(n)-1)/2$$m$$O(m^2)$$A$ para cada t = 0 , 1 , 2 , … log ( n ) - 1 , terminando em O ( n 2 log ( n ) 3 ) .$O((n\log n)^2)$$t=0, 1, 2, \dots \log(n)-1$$O(n^2 \log(n)^3)$

ps. Eu mostro que o teste de igualdade em cadeias de bits com bits não pode ser mais rápido do que o teste de síndrome em cadeias com m bits (sabe-se que a síndrome leva pelo menos O ( m 2 ) tempo). Podemos modificar qualquer algoritmo de TM para teste de igualdade para resolver palíndromo. Suponha que a TM de teste de igualdade comece com dois números inteiros: um à esquerda da cabeça, um à direita (este é o formulário de entrada mais simples para a TM). Cada movimento sobre as posições da esquerda pode ser espelhado (refletido) sobre as posições da direita. Construímos uma TM espelhada: sempre que a TM inicial estiver em uma posição - x < 0 (à esquerda), a TM espelhada estará na posição $m$$m$$O(m^2)$$-x<0$$x$(a direita). Se um TM resolvesse o teste de igualdade em menos de , esse TM espelhado modificado resolveria o palíndromo em menos de O ( m 2 ) .$O(m^2)$$O(m^2)$

Além disso, existem alguns algoritmos de TM para teste de igualdade e todos eles exigem tempo quadrático porque precisam de zigue-zague, veja, por exemplo, o Exemplo 2 da Máquina de Turing em cursos.cs.washington.edu/courses/cse431/14sp/scribes/ lec3.pdf