Le compromis espace-temps et le meilleur algorithme

Considérons un langage tel que: $L$

$L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$

et pour que

$L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$

En d'autres termes, la machine la plus rapide calcule dans le temps et la machine la plus économe en espace calcule tout en utilisant l'espace . $M$ $L$ $O(f(n))$ $M'$ $L$ $O(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 dans que pouvons-nous dire de la machine la plus économe en espace dans ? Qu'en est- il de la même chose pour la version spatiale évidente: . $\mathbb{M}_T$ $L$ $O(f(n))$ $\mathbb{M}_T$ $\mathbb{M}_S$

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

cc.complexity-theory ds.algorithms open-problem space-time-tradeoff 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

Alors, prenez une langue décidable

. Ce langage donne des fonctions

pour que

L

$L$

f_{L}, g_{L}

$f_L, g_L$

L \in TIME [f_{L} (n)] \cap SPACE [g_{L} (n)]

$L \in \text{TIME}[f_L(n)] \cap \text{SPACE}[g_L(n)]$

L \notin TIME [o (f_{L} (n))] \cup SPACE [o (g_{L} (n))]

$L \not\in \text{TIME}[o(f_L(n))] \cup \text{SPACE}[o(g_L(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

En relation? Limites inférieures du compromis espace-temps

Tsuyoshi Ito

Réponses:

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 $\mathsf{DTIME}(t(n)) \subseteq \mathsf{DSPACE}(t(n)/log(n))$

vzn
la source

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

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