De grands écarts entre la RAM et la complexité de la machine Turing

Si nous considérons uniquement les problèmes dans P, y a-t-il de grands écarts entre l'algorithme de RAM de mots connu le plus rapide et l'algorithme de machine de Turing le plus rapide connu pour des problèmes particuliers? Je suis particulièrement intéressé s'il existe de grandes lacunes pour les problèmes naturels d'intérêt général.

cc.complexity-theory ds.algorithms Lembik
la source

une machine RAM peut être simulée par une machine Turing avec une surcharge de

en runtime. Il n'y aura donc pas de très grandes lacunes.

O (n \log n)

$O(n\log n)$

Shaull

@Shaull Existe-t-il un écart de cette taille pour tout problème naturel / populaire?

Lembik

Palindrome prend du temps

sur une TM à bande unique (et est

dans la RAM). eecs.yorku.ca/course_archive/2008-09/W/6115/palindrome.pdf

Ω (n^{2})

$\Omega(n^2)$

O (n)

$O(n)$

SamM

Le commentaire de Shaull n'est vrai que pour les machines non déterministes et dans le cadre de deux bandes TM, pour autant que je sache. Citation, Shaull?

Ryan Williams

@ qbt937 - Wow, quelle explosion du passé :) Je crois que je n'ai pas fourni de citation parce que je n'en avais pas (et je n'en ai pas maintenant), et il se pourrait bien que Ryan Williams ait raison.

Shaull

Réponses:

Il est connu que tout problème que vous pouvez calculer sur une machine RAM au temps , vous pouvez le faire dans une machine de Turing à temps au plus . Vous devez noter que la taille totale de la mémoire utilisée ne peut pas être supérieure à , car cela signifierait que vous avez effectué plus d'opérations d'écriture que , donc chaque fois que vous récupérez quelque chose dans la mémoire RAM, le Turing la machine prendrait dans le pire des cas $T(n)$ $T(n)^2$ $T(n)$ $T(n)$ $T(n)$ le temps de trouver séquentiellement l'élément souhaité dans la bande. Outre l'accès à la mémoire, le reste des opérations devrait prendre environ le même temps. Et ainsi vous obtenez la limite.

Javier Cano
la source

Les RAM peuvent calculer la longueur de l'entrée (et donc aussi la partie de cette longueur) en temps logarithmique, mais les machines de Turing de base ont besoin d'un temps linéaire pour calculer cette parité.

$A$ $O(n\log(n))$ $O(n^2 \log(n)^3)$ $A$

$O(T(n)^2)$ $O(T(n))$ $A$ $A$ $O(n\log(n))$ $A$ $O(T(n)^2)$ $O(T(n)n\log(n))$

$\texttt{tab}$ $n=2k$ $\log(n)$ $\texttt{d}$ $\log(n)$ $\log(n)$ $t\in[0..\log(n)-1]$ $X_t=1$ $\texttt{tab}[i]$ $\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$ $n\log(n)+\log(n)\log(n)$

$A$ $w=\log(n)$ $O(n\log(n)+\log(n)^2)$ $O(n\log(n))$ $\log(n)$ $A$ $X_t$ $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))$ $A$ $O(n\log(n))$

$A$ $O(n^2 \log(n)^2)$ $t$ $A_t$ $O(n\log(n))$ $\texttt{tab}[i]$ $\texttt{d}[t]$ $0$ $\texttt{tab}[i]$ $A_t$ $n(\log(n)-1)/2$ $m$ $O(m^2)$ $A$ $O((n\log n)^2)$ $t=0, 1, 2, \dots \log(n)-1$ $O(n^2 \log(n)^3)$

$m$ $m$ $O(m^2)$ $-x<0$ $x$ $O(m^2)$ $O(m^2)$

En outre, il existe des algorithmes TM de test d'égalité et tous nécessitent un temps quadratique car ils ont besoin d'un zigzag, voir par exemple l'exemple 2 de la machine de Turing à courses.cs.washington.edu/courses/cse431/14sp/scribes/ lec3.pdf

Daniel Porumbel
la source

La limite inférieure pour les palindromes ne s'applique qu'au modèle à bande unique non naturel. Il est simple de tester l'égalité de deux chaînes sur une MT en temps linéaire. Il en va de même pour l'égalité de deux séquences d'entrées plus longues. De plus, pour que la question ait un sens, les entrées des deux modèles de machine doivent être identiques, c'est-à-dire écrites sous forme de chaînes sur un alphabet fini. Ainsi, votre RAM aurait besoin de temps O (log n) pour lire chaque entrée et la convertir en un mot, rendant cette opération inutile.

Emil Jeřábek

@Emil Jeřábek, je vais modifier ma réponse pour indiquer que je ne pense qu'à la 1-tape TM. Lorsque vous dites qu'une MT peut tester l'égalité en temps linéaire, je suppose que vous pensez à une MT à 2 bandes. Cependant, j'ai compris que toute la question concernait les MT à 1 bande. En ce qui concerne le formulaire de saisie, je dois avouer que vous avez peut-être raison, au moins pour certains mots-RAM. Mais pour autant que je sache, un tableau int C ++ stocke les entiers les uns après les autres sans séparateur, comme s'ils stockaient ensemble une séquence de bits. 10 pouces sur 16 bits occupent exactement 160 bits, non? Même si ce n'est pas le cas, on pourrait construire une machine fonctionnant ainsi.

Daniel Porumbel

Le modèle de machine de Turing standard dans la théorie de la complexité est multi-bandes. Je ne vois pas en quoi le C ++ est pertinent, nous ne discutons pas du C ++, mais du modèle RAM. Dans ce modèle, les emplacements de mémoire individuels peuvent contenir des nombres de longueur

, mais nous ne pouvons toujours opérer que sur un (ou

O (\log n)

$O(\log n)$

O (1)

$O(1)$

\log n

$\log n$

Il existe deux possibilités: (1) L'emplacement d'entrée [0] contient le premier bit du premier nombre, l'emplacement [1] contient le deuxième bit du premier nombre, etc. Ensuite, il faut

O (n \log n)

$O(n\log n)$

@Emil Jeřábek, Suite à vos remarques, j'ai édité la question pour proposer un problème et un algorithme RAM qui prend explicitement

O (n \log (n))

$O(n\log(n))$