Le compromis espace-temps et le meilleur algorithme

14

Considérons un langage tel que:L

LDTIME(O(f(n)))DSPACE(O(g(n)))

et pour que

LDTIME(o(f(n)))DSPACE(o(g(n)))

En d'autres termes, la machine la plus rapide calcule L dans le temps O ( f ( n ) ) et la machine M ' la plus économe en espace calcule L tout en utilisant l'espace O ( g ( n ) ) .MLO(f(n))MLO(g(n))

Que dire de l'efficacité spatiale de M ou de l'efficacité temporelle de M '? Ou plus précisément, si est l'ensemble de toutes les machines qui calculent L dans O ( f ( n ) ), que pouvons-nous dire de la machine la plus économe en espace dans M T ? Qu'en est- il de la même chose pour la version spatiale évidente: M S .MTLO(f(n))MTMS

Alternativement, et g ( n ) peuvent-ils être utilisés pour définir de bons compromis espace-temps? Dans quelles conditions est T S o ( f ( n ) g ( n ) ) ou plus généralement pour un compromis espace-temps h ( T , S ) dans quelles conditions est h ( T , S ) h ( o ( f ( n ) )f(n)g(n)TSo(f(n)g(n))h(T,S) .h(T,S)h(o(f(n)),o(g(n)))

Artem Kaznatcheev
la source
Demandez-vous un L arbitraire, ou êtes-vous intéressé par des résultats de cette nature qui pourraient exister pour des problèmes spécifiques?
Suresh Venkat
Je m'intéresse vraiment aux deux. Ma motivation d'origine était principalement due à des problèmes d'accessibilité (connectivité st dirigée et non dirigée). Cependant, il serait intéressant de savoir s'il existe des limites ou des techniques générales disponibles.
Artem Kaznatcheev
2
Alors, prenez une langue décidable . Ce langage donne des fonctions f L , g L pour que L TIME [ f L ( n ) ] SPACE [ g L ( n ) ] et L TIME [ o ( f L ( n ) ) ] SPACE [ o ( g L ( n ) ) ]LfL,gLLTIME[fL(n)]SPACE[gL(n)]LTIME[o(fL(n))]SPACE[o(gL(n))]. (Est-ce vrai, ou y a-t-il des langages "d'accélération" qui le violent?)
Derrick Stolee
Plus précisément, il existe des exemples dans la recherche par plage de problèmes qui admettent (requête, espace) de la forme (log n, poly (n)), ou (sublinéaire, linéaire), ou toute interpolation de ceux
Suresh Venkat

Réponses:

14

Les f et g prototypiques ici seraient probablement l'espace poly-temps et polylog. Le problème intéressant ici est la connectivité (dans les graphes dirigés) qui peut être résolue en temps polynomial (en utilisant l'espace linéaire) ou en espace polylog (en utilisant le temps super-polynomial). C'est un problème ouvert célèbre s'il peut être résolu dans TIME-SPACE (poly, polylog), une classe connue sous le nom de SC .

C'est-à-dire que votre question est un problème ouvert bien connu. Je ne pense pas que quelque chose de non trivial soit connu ici.

Noam
la source
Merci d'avoir répondu. Je soupçonnais que ce serait un problème ouvert, mais j'espère que certains résultats spécifiques seront déjà connus. Malheureux :(.
Artem Kaznatcheev
-4

cette question est apparue sur des "questions similaires" lorsque je viens de publier cette autre question /cstheory/9677/deterministic-time-space-separation-via-space-compression .

là je cite hopcroft, paul, vaillants 1977 résultat (apparemment le plus connu selon rj lipton dans son blog) qui semble s'appliquer à votre question ie TjeME(t(n))SPUNECE(t(n)/log(n))

vzn
la source
1
Je ne vois pas comment cela s'applique aux compromis spatio-temporels ...
Artem Kaznatcheev
le concept de "compromis espace-temps" ne semble pas être exactement défini. ma réponse peut être comprise comme suit: un programme qui est en DTIME (t (n)) est "naturellement" en DSPACE (t (n)). les résultats du HPV1977 permettent alors de construire une MT, au détriment d'une certaine augmentation des états (et des bandes peut-être?) de sorte qu'il faut plutôt de l'espace DSPACE (t (n) / log (n)). donc un "compromis"
vzn
1
Il y a une compréhension standard des compromis dans CS qui n'est pas du tout ce que vous décrivez (ce que vous décrivez n'est pas du tout un compromis, mais juste une relation standard entre DTIME et DSPACE). De plus, j'explique explicitement ce que je veux dans le compromis espace-temps dans ma question, veuillez lire attentivement les questions avant d'essayer d'y répondre.
Artem Kaznatcheev
si votre définition des compromis temps-espace ci-dessus dans votre question est standard comme vous le dites, est-elle définie dans une quelconque littérature?
vzn
En regardant votre définition, il semble intuitivement plausible que de tels f (n), g (n) existent pour toutes les langues décidables mais ne rencontrerait pas de problèmes même en prouvant que ces f (n), g (n) existent nécessairement en raison du théorème d'accélération de Blum ....?
vzn