Le temps et l'espace mémoire sont les deux principales contraintes sur ce que nous pouvons calculer, et comprendre leur relation est un élément clé de la recherche de complexité informatique
Comment le temps et l'espace sont-ils liés au calcul? Nous avons une nouvelle réponse
Une découverte étonnante de la relation entre la quantité de mémoire dont un calcul nécessite et combien de temps il faut a séduit les informaticiens – bien qu'il ne soit pas clair s'il existe des applications pratiques.
«Cela secoue en quelque sorte ma vision du monde», explique Ryan Williams au Massachusetts Institute of Technology, qui a fait la découverte. «Je suis toujours choqué que ça existe même.»
Le temps et l'espace mémoire sont les deux principales contraintes sur ce que nous pouvons calculer. Certains problèmes nécessitent beaucoup de mémoire, beaucoup de temps et beaucoup exigent beaucoup des deux. L'étude de ces contraintes est le domaine des chercheurs de complexité de calcul, qui appellent le temps comme le nombre d'étapes qu'un ordinateur prend pour effectuer une certaine tâche et l'espace comme le nombre de créneaux de mémoire que nécessite la tâche.
Intuitivement, ces valeurs sont liées, car si une tâche nécessite des étapes x, dans le pire des cas où l'ordinateur doit accéder à sa mémoire pour chaque étape, il nécessitera des emplacements de mémoire x.
Mais les chercheurs ont pu réduire la barre pour la quantité de mémoire nécessaire dans ce pire des cas. Dans les années 1970, il a été découvert que, en fait, tout calcul qui prend des étapes X pouvait être effectué avec x / log x de mémoire. Ainsi, un programme qui a fait 100 pas de temps, par exemple, pourrait toujours fonctionner dans les 50 emplacements de mémoire, car le journal 100 est égal à 2.
«C'est le meilleur que nous ayons connu jusqu'à la semaine dernière», explique Lance Fortnow à l'Illinois Institute of Technology. Mais alors Williams a publié un article surprenant qui a montré que cela peut être considérablement réduit – à la racine carrée de x log X. Au lieu de 100 ou 50 emplacements de mémoire, un problème en 100 étapes pourrait en fait être réduit à 15 emplacements.
«C'était un peu un choc quand Ryan a envoyé ce journal la semaine dernière, et nous étions tous comme« Wow »», explique Fortnow.
Williams lui-même a été également surpris. «Il m'a fallu des mois pour me convaincre que ce n'était pas seulement faux», dit-il. «C'est toujours très difficile pour moi de me terminer la tête. Je peux passer par toutes les étapes, la preuve et vérifier que chaque étape est correcte et que c'est vrai. Mais à la fin, je me demande toujours.
La découverte semble peu probable car cela signifie que les ordinateurs semblent avoir seulement assez d'espace pour contenir une petite partie d'un problème en mémoire – un peu comme les humains en mesure de résoudre un problème de mathématiques complexes et multi-étapes sans avoir tout besoin de tout écrire, en s'appuyant uniquement sur notre mémoire à court terme limitée.
L'approche de Williams dépend de ce que l'on appelle le problème d'évaluation des arbres. Cela implique une série de calculs liés dans une structure en forme d'arbre ramifiée, où le calcul du résultat final à la «racine» de l'arbre implique d'abord de calculer les «feuilles», puis les «branches», etc. Des progrès récents dans la résolution du problème d'évaluation des arbres ont montré qu'il est possible de le faire avec un algorithme capable de réutiliser la mémoire informatique qui est déjà pleine – elle-même une découverte complètement inattendue.
Pour mettre cela à ce sujet sur la question du temps et de l'espace, Williams a créé un modèle qui peut représenter tout problème de calcul, puis a appliqué le nouvel algorithme d'évaluation des arbres, montrant qu'il pourrait réduire considérablement la quantité de mémoire requise. Cela implique des astuces mathématiques et des «annulations magiques» qui fournissent finalement des réponses valides, dit-il.
« Cela semble plus excitant », explique Ian Mertz à l'Université Charles en République tchèque, l'un des chercheurs qui a développé le nouvel algorithme. « Certainement un résultat contre-intuitif, même si je dirais que nos algorithmes d'évaluation des arbres étaient déjà assez contre-intuitifs. »
Mais bien que l'ampleur de la découverte ait choqué les informaticiens, il ne changera pas nécessairement la façon dont nous utilisons les ordinateurs. Le problème est que la découverte montre que même si vous pouvez réduire la quantité de mémoire requise pour effectuer un calcul, cela ne diminuera pas le temps pris. La mémoire de l'ordinateur est assez bon marché et facilement disponible, donc réduire le montant dont nous avons besoin n'est pas une priorité.
Une découverte qui permettait l'inverse signifierait que nous pourrions ajouter plus de mémoire aux ordinateurs et accélérer le calcul en conséquence – quelque chose qui serait très utile car les progrès de la vitesse du processeur ont commencé à ralentir – mais si cela serait possible n'est pas clair. « Maintenant que nous savons que des algorithmes économes en temps peuvent être économes en espace, nous pouvons rechercher des compromis qui sont assez bons pour le temps et l'espace en même temps, et c'est utile dans un sens réel », explique Mertz.
Fortnow dit qu'il ne voit aucune implication pratique immédiate pour le travail, mais souligne qu'elle donne l'espoir que davantage de surprises dans la complexité de calcul pourraient encore venir et qu'ils pourraient secouer comment nous résolvons des problèmes difficiles. « Vous êtes choqué une fois, vous pouvez à nouveau être choqué », dit-il.
