Solutionneur de problèmes universel efficace?

Définissez un "problème" comme étant un algorithme acceptant un nombre naturel et renvoyant 0 ou 1 qui renvoie sur au moins un . Un tel est appelé une "solution" à $A$ $1$ $n \in \mathbb{N}$ $n$ $A$

Définir un "solutionneur de problèmes universel" comme étant un algorithme acceptant un problème et renvoyant l'une de ses solutions. Par exemple, peut fonctionner en bouclant sur tous les nombres naturels et en exécutant son entrée sur eux jusqu'à résultat (il ne doit s'arrêter que sur une entrée valide) $U$ $U$ $1$

Je suis intéressé à explorer les limites de performance sur les résolveurs de problèmes universels

Étant donné un résolveur de problèmes universel et un problème, notons le temps qu'il faut à pour produire une sortie lors de l'acceptation de l'entrée $U$ $A$ $t(U, A)$ $U$ $A$

Un résolveur de problèmes universel est appelé "efficace" lorsque, pour tout résolveur de problèmes universel , nous avons $U$ $V$

t (U, A) < t (V, A) + t_{V}

$t(U, A) < t(V, A) + t_V$

Ici, dépend de mais ne dépend pas de $t_V$ $V$ $A$

Existe-t-il des résolveurs de problèmes universels efficaces?

EDIT: J'ai réalisé qu'il était possible de changer les définitions de "problème" et "solutionneur de problème universel" en quelque chose d'un peu plus élégant et essentiellement équivalent. Un "problème" est un algorithme sans entrée retournant 0 ou 1 (qui s'arrête). Un "solutionneur de problèmes universel" est un algorithme acceptant un problème et renvoyant son résultat. C'est plus ou moins une machine de Turing universelle

L'ancienne définition peut être réduite à une nouvelle définition, car étant donné un problème dans l'ancien sens, nous pouvons construire un problème dans le nouveau sens qui applique simplement le solveur universel trivial à l'ancien sens à (le solveur décrit dans le texte ci-dessus). ) $A$ $B$ $A$

La nouvelle définition peut être réduite à l'ancienne définition, étant donné que un problème dans le nouveau sens, nous pouvons construire un problème dans l'ancien sens qui calcule simplement et compare l'entrée au résultat $B$ $A$ $B$

L'exemple trivial d'un résolveur de problèmes universel nouveau sens est un algorithme qui exécute simplement son entrée

cc.complexity-theory ai.artificial-intel Vanessa
la source

Réponses:

Il n'y a pas de solution universelle efficace aux problèmes. Intuitivement, U devrait avoir le temps d'exécution (presque) optimal pour tout problème de décision décidable; tandis que le théorème de l'accélération dit qu'il existe des problèmes de décision décidables qui n'ont pas d'algorithme optimal (même pas dans un sens très doux). Pour formaliser cela:

Le théorème d'accélération du temps (voir par exemple [1])): Pour chaque fonction calculable (et super-linéaire) il existe un ensemble décidable tel que si alors pour satisfaisant . $g$ $S$ $S \in DTIME(t)$ $S \in DTIME(t')$ $t'$ $g(t'(n)) < t(n)$

Dans ce qui suit, nous travaillons avec la deuxième définition. Soit tout solveur universel. Laissez et soit un algorithme qui décide . Soit la TM sans entrée st . Il existe un TM avec environ une surcharge logarithmique au moment de l'exécution (le codage de et ne diffère que par ). Par l'accélération thoerem, il y a un TM qui décide et . Nous avons donc . $U$ $g(n)=2^{2n}$ $A$ $S$ $A_i$ $A_i = A(i)$ $\tilde U(i)=U(A_i)$ $A$ $A_i$ $O(\log i)$ $B$ $S$ $2^{ 2 TIME(B)} < TIME(\tilde U)$ $2^{TIME(B)} < TIME(\{U(A_i)\})$

Soit un résolveur de problèmes universel tel que pour l'entrée , il simule avec une surcharge logarithmique dans le temps. (De toute évidence, les fonctions d'exécution de et sont pas limitées) Nous avons donc $V$ $A_i$ $B(i)$ $A(i)$ $B(i)$

$\forall c \; \exists A_i \;\; t(U, A_i) > t(V, A_i) +c$

Donc ne peut pas être efficace. $U$

[1] Oded Goldreich, Complexité computationnelle, une perspective conceptuelle, théorème 4.8. Le chapitre 4.2.1.2 est également pertinent.

Ruhollah Majdoddin
la source

Excellente solution, merci!

Vanessa

L'algorithme universel de Levin est un algorithme tel que . En modifiant l'algorithme (voir par exemple l'algorithme de Hutter le plus rapide et le plus court pour tous les problèmes bien définis ), vous pouvez faire de une constante universelle, mais certainement pas comme vous le souhaitez. Pour les travaux connexes, consultez les travaux de Hirsch, Itsykson et leurs étudiants, par exemple ce rapport technique . $t(U,A) < s_V t(V,A) + t_V$ $s_V$ $1$

Edit: Comme le fait remarquer Squark, le temps d'exécution de l'algorithme de Levin dépend également du temps d'exécution de , car il doit vérifier ses réponses. Pour obtenir un constant , tout ce que vous devez faire est de définir les vitesses des différents algorithmes en progression géométrique (plutôt qu'en progression arithmétique, comme dans l'algorithme original de Levin). $A$ $s_V$

Yuval Filmus
la source

Si je comprends bien, de Levin est quelque chose du genre "exécutons tous les algorithmes possibles en parallèle, et chaque fois que l'un d'eux produit une réponse, testons-la et arrêtons si elle est correcte". Puisque V est l'un des algorithmes que U exécute, il trouvera la réponse en même temps que V jusqu'à un ralentissement lié à la fraction de "temps CPU" allouée au "thread" de V. Cependant, je pense qu'il vous manque un terme dépendant de A supplémentaire: le temps nécessaire pour tester la réponse. L'algorithme de Hutter repose sur la recherche de preuves, ce qui ne me suffit pas puisque je ne fais aucune hypothèse sur la prouvabilité

U

$U$

Vanessa

Yuval, il me manque quelque chose. Dans quel sens devient constant? Cela dépend toujours de puisque différents algorithmes fonctionnent avec une vitesse différente, quelle que soit la progression que vous utilisez, non?

s_{V}

$s_V$

V

$V$

Vanessa

Je crois que vous pouvez (uniformément) lier au prix de faire croître encore plus follement (mais toujours constant pour tout donné ).

s_{V}

$s_V$

t_{V}

$t_V$

V

$V$

Yuval Filmus

Je ne comprends pas comment. Btw si j'ajoutais que la condition V est un solutionneur de problèmes universel, il serait possible d'éliminer le terme dépendant de A en exécutant uniquement des algorithmes qui peuvent être prouvés être des résolveurs de problèmes universels

Vanessa