Raum-Zeit-Kompromiss und der beste Algorithmus

Betrachten Sie eine Sprache so, dass: $L$

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

und so das

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

Mit anderen Worten, die schnellste Maschine berechnet in der Zeit und die platzsparendste Maschine berechnet unter Verwendung des Raums . $M$ $L$ $O(f(n))$ $M'$ $L$ $O(g(n))$

Was kann über die Raumeffizienz von M oder die Zeiteffizienz von M 'gesagt werden? Genauer gesagt, wenn die Menge aller Maschinen ist, die in berechnen, was können wir dann über die platzsparendste Maschine in sagen ? Wie steht es mit der offensichtlichen Space-Version: . $\mathbb{M}_T$ $L$ $O(f(n))$ $\mathbb{M}_T$ $\mathbb{M}_S$

Alternativ können und verwendet werden, um einige gute Raum-Zeit-Kompromisse zu definieren? Unter welchen Bedingungen ist oder allgemeiner für einen Raum-Zeit-Kompromiss unter welchen Bedingungen ist . $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
quelle

Fragen Sie nach einem beliebigen L oder interessieren Sie sich für Ergebnisse dieser Art, die für bestimmte Probleme vorliegen könnten?

Suresh Venkat

Ich interessiere mich wirklich für beides. Meine ursprüngliche Motivation beruhte hauptsächlich auf Erreichbarkeitsproblemen (gerichtete und ungerichtete st-Konnektivität). Es wäre jedoch interessant zu wissen, ob allgemeine Grenzen oder Techniken verfügbar sind.

Artem Kaznatcheev

Also, nehmen Sie jede entscheidbar Sprache . Diese Sprache gibt Funktionen so dass und . (Stimmt das, oder gibt es "Speedup" -Sprachen, die dagegen verstoßen?)

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))]$

Derrick Stolee

Insbesondere gibt es Beispiele für die Bereichssuche von Problemen, die (Abfrage, Leerzeichen) der Form (log n, poly (n)) oder (sublinear, linear) oder eine Interpolation davon

zulassen

Verbunden? Raum-Zeit-Kompromiss untere Schranken

Tsuyoshi Ito

Antworten:

Das prototypische f und g wäre hier wahrscheinlich Polyzeit und Polylograum. Das interessante Problem hierbei ist die Konnektivität (in gerichteten Graphen), die in Polynomzeit (unter Verwendung des linearen Raums) oder im Polylograum (unter Verwendung der Superpolynomzeit) gelöst werden kann. Es ist ein bekanntes offenes Problem, ob es mit TIME-SPACE (Poly, Polylog), einer Klasse namens SC , gelöst werden kann .

Dh Ihre Frage ist ein bekanntes offenes Problem. Ich glaube nicht, dass hier etwas Nicht-Triviales bekannt ist.

Noam
quelle

Danke für die Antwort. Ich hatte den Verdacht, dass dies ein offenes Problem sein würde, hoffte jedoch, dass einige konkrete Ergebnisse bereits bekannt sein würden. Leider :(.

Artem Kaznatcheev

-4

Diese Frage tauchte bei "ähnlichen Fragen" auf, als ich gerade diese andere Frage stellte: /cstheory/9677/deterministic-time-space-separation-via-space-compression .

dort zitiere ich hopcroft, paul, valiants 1977 resultat (anscheinend am bekanntesten nach rj lipton in seinem blog), das auf deine frage zutrifft dh $\mathsf{DTIME}(t(n)) \subseteq \mathsf{DSPACE}(t(n)/log(n))$

vzn
quelle

Ich verstehe nicht, wie dies auf Zeit-Raum-Kompromisse

zutrifft

Der Begriff "Zeit-Raum-Kompromiss" scheint nicht genau definiert zu sein. Meine Antwort kann wie folgt verstanden werden: Ein Programm, das sich in DTIME (t (n)) befindet, ist "natürlich" in DSPACE (t (n)). Die HPV1977-Ergebnisse ermöglichen es dann, eine TM auf Kosten einer gewissen Zunahme der Zustände (und möglicherweise der Bänder?) so zu konstruieren, dass stattdessen DSPACE (t (n) / log (n)) Speicherplatz benötigt wird. daher ein "Kompromiss"

vzn

Es gibt ein Standardverständnis für Kompromisse in CS, das nicht das ist, was Sie beschreiben (was Sie beschreiben, ist überhaupt kein Kompromiss, sondern nur eine Standardbeziehung zwischen DTIME und DSPACE). Außerdem erkläre ich in meiner Frage ausdrücklich, was ich im Zeit-Raum-Kompromiss möchte. Bitte lies die Fragen sorgfältig durch, bevor du versuchst, sie zu beantworten.

Artem Kaznatcheev

Wenn Ihre Definition der Zeit-Raum-Kompromisse oben in Ihrer Frage Standard ist, wie Sie sagen, ist sie in irgendeiner Literatur definiert?

vzn

Wenn Sie Ihre Definition überblicken, erscheint es intuitiv plausibel, dass solche f (n), g (n) für alle entscheidbaren Sprachen existieren, aber es würde nicht zu Problemen kommen, selbst wenn man beweisen würde, dass solche f (n), g (n) notwendigerweise aufgrund des Satzes zur Beschleunigung des Blums existieren ....?

vzn