Dans quelles circonstances les algorithmes

16

Supposons que, pour chaque , il existe une machine de Turing qui décide d'un langage dans le temps . Existe-t-il un seul algorithme déterminant dans le temps ? (Ici, le terme est mesuré en termes de , la longueur d'entrée.)ϵ>0MϵLO(na+ϵ)LO(na+o(1))o(1)n

Cela fait-il une différence si les algorithmes sont calculables, ou efficacement calculables, en termes de ?Mϵϵ

Motivation: dans de nombreuses preuves, il est plus facile de construire des algorithmes de temps que l'algorithme limitant . En particulier, vous devez délimiter le terme constant dans pour passer à la limite . Ce serait bien s'il y a un résultat général que vous pouvez invoquer pour passer directement à la limite.O(na+ϵ)O(na+o(1))O(na+ϵ)O(na+o(1))

David Harris
la source

Réponses:

10

La question est similaire aux questions sur l'existence constructive de la limite d'une séquence d'objets (constructifs). Habituellement, si vous pouvez construire ces objets de manière uniforme (ici Mϵ ) suffisamment efficacement, vous pouvez montrer l'existence de la limite de manière constructive.

Par exemple, supposons que nous avons un TM qui exécute M | k | - 1 sur x et son temps d'exécution est O ( n a + | k | - 1 ) + O ( | k | ) (ici les bornes sont également uniformes, par exemple quelque chose comme O ( 2 k . N a + | k | - 1 )N(k,x)M|k|1xO(na+|k|1)+O(|k|)O(2k.na+|k|1)ne fonctionnerait pas). Ensuite, nous pouvons combiner ce simulateur uniforme avec la fonction pour obtenir la machine N ( x , x ) qui fonctionne dans le temps O ( n a + o ( 1 ) ) .(k,x)xN(x,x)O(na+o(1))

PS: est un peu ambigu en raison de l'imbrication de notations asymptotiques, je l'interprète comme n a + o ( 1 ) . Nous avons également besoin d' un pour ne pas être trop petit, par exemple au moins 1 .O(na+o(1))na+o(1)a1

Kaveh
la source
8

Vous pouvez utiliser l'algorithme de recherche universel de Levin. Supposons que vous puissiez en quelque sorte énumérer une séquence d'algorithmes décidant L , chacun fonctionnant dans le temps C k n a + 1 / k . L'algorithme de Levin fonctionne dans le temps T ( n ) D k n a + 1 / k pour chaque k , où D k est une constante dépendant de C k . Donc pour tout k , τ ( n ) AkLCkna+1/kT(n)Dkna+1/kkDkCkk Étant donnéϵ>0, choisissezk=2/ϵ, et soitN=D 2 / ϵ k. Alors pournN,τ(n)ϵ. Doncτ(n)0, et nous obtenons que l'algorithme de Levin fonctionne dans le tempsna+τ(n)=na+

τ(n)logT(n)lognalogDk+(a+1/k)lognlogna=logDklogn+1k.
ϵ>0k=2/ϵN=Dk2/ϵnNτ(n)ϵτ(n)0 .na+τ(n)=na+o(1)
Yuval Filmus
la source
Si je comprends l'algorithme de Levin, cela ne s'applique qu'aux algorithmes de recherche. Cet algorithme fonctionnerait pour inverser une fonction , où f peut être calculé dans le temps O ( n o ( a ) ) . ffO(no(a))
David Harris
Je ne suggère pas d'utiliser l'algorithme de Levin lui-même, juste l'idée d'exécuter tous les algorithmes en parallèle en utilisant la queue d'aronde, de telle sorte que chacun ne soit ralenti que par un facteur multiplicatif. Ak
Yuval Filmus
@ Yuval, lorsque vous associez tous les algorithmes, comment décidez-vous quelle réponse accepter? Dans un problème de recherche, vous pouvez tester chaque sortie putative, mais en général ce n'est pas possible.
David Harris
J'accepte la première réponse qui apparaît. On nous donne que les algorithmes correctement décider L . AkL
Yuval Filmus