Bonjour,
j'ai trouvé un résultat en th. de la complexité :
Soit Pt un algorithme.
Il existe un algorithme Pe tel que :
Temps(Pt, X) > (Espace(Pe, X) - |X|)^2
C'est valable pour une machine de Turing ou une machine RAM
Est-ce que c'est un résultat qui vaut la peine ?
Où déjà trouvé depuis longtemps ? Ou trop simple ?
Re : Complexité algorithmique
Bon
pas de réponse
Ca doit être bidon
salut tu peux expliquer un peu plus ce que tu entends par Temps(pt,X), |X| et espace(Pe,X) ?
Oui j'ai pas été assez clair. Donc :
Soit L un langage et Pt un algorithme qui décide L. (sur une machine de Turing).
Alors il existe un algorithme Pe qui décide aussi L, tel que :
Pour toute instance X en entrée, on a
Temps(Pt, X) > (Espace(Pe, X) - |X|)^2
Avec Temps(P, X) le temps que met P à décider l'instance X. et Espace(P, X) l'espace que met P à décider X.
En gros, le temps minimal d'un langage est égal au carré de son espace minimal. (sauf pour le cas où l'espace est petit, d'où le '- |X|' dans l'expression)
