Eine explizite Trennung zwischen Zeitkonstruierbarkeit und Raumkonstruierbarkeit?

Zeigen Sie eine Funktion die räumlich, aber nicht zeitlich konstruierbar ist. $f(n)$

Hängt dieses Problem mit einer möglichen Trennung zwischen den Komplexitätsklassen DTIME (f (n)) und SPACE (f (n)) zusammen?

cc.complexity-theory space-bounded separation Tian Liu
quelle

en.wikipedia.org/wiki/Constructible_function Soweit ich weiß, hat diese Frage nichts mit TIME (f (n)) und SPACE (f (n)) zu tun. Beachten Sie jedoch, dass diese beiden Klassen bekanntermaßen unterschiedlich sind. Suchen Sie nach den Artikeln "On Time Versus Space", "On Time Versus Space II", "On Time Versus Space III"

Ryan Williams

Eine kurze Beobachtung: Ich denke, dass das Problem der Frage entspricht, ob DTIME (f (n)) ALLTALLY und SPACE (f (n)) ∩TALLY für eine raumkonstruierbare Funktion f (n) unterschiedlich sein können, wobei TALLY ist die Klasse der Sprachen, die Teilmengen von 1 ^ * sind.

Tsuyoshi Ito

Hoppla, sie sind möglicherweise nicht gleichwertig. Hier ist ein Beweis für eine Richtung. Wenn es eine Sprache L = {1 ^ n | gibt n∈S} ∈ TALLY∩ (SPACE (f (n)) ∖ DTIME (f (n))) für eine raumkonstruierbare Funktion f (n), dann sowohl f (n) als auch f (n) + χ_S (n ) (wobei χ_S (n) die charakteristische Funktion von S ist) sind räumlich konstruierbar, aber nicht beide sind zeitlich konstruierbar, und daher ist mindestens eine von ihnen eine raumkonstruierbare, aber nicht zeitkonstruierbare Funktion.

Tsuyoshi Ito

Dank Ryan weiß ich durch Ihren Kommentar, dass TIME (f (n)) in SPACE (f (n) / log f (n)) von Hopcroft et al. Enthalten ist und letzteres ordnungsgemäß in SPACE (f (n) enthalten ist )) nach dem Satz der Raumhierarchie.

Tian Liu

Dank Tsuyoshi, sehr kluge Ideen, wenn sowohl f (n) als auch f (n) + χ_S (n) zeitkonstruierbar sind, können wir entscheiden, ob n∈S höchstens f (n) + 1 Zeit beträgt, also L. ∈TALLY ∩ DTIME (f (n)), ein Widerspruch. Aber können Ihre Konstruktionen "explizieren" genannt werden? welches ist nicht zeitkonstruierbar, f (n) oder f (n) + χ_S (n)? Mit "explizit" meine ich, dass wir den Wert f (n) für alle n bestimmen können, dann ist Ihre Konstruktion explizit.

Tian Liu

Antworten:

Eine Funktion ist zeitlich konstruierbar, wenn es eine Turingmaschine die bei Eingabe die Funktion in der Zeit berechnet . $T \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto T(|x|)$ $O(T(n))$

Eine Funktion ist wenn es eine Turingmaschine die bei Eingabe die Funktion im Raum berechnet . $S \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto S(|x|)$ $O(S(n))$

Einige Texte erfordern, dass die zeitlich / räumlich konstruierbaren Funktionen nicht abnehmen. Einige Texte erfordern, dass die zeitkonstruierbaren Funktionen erfüllen und die raumkonstruierbaren Funktionen erfüllen . Einige Texte verwenden in der Definition nicht die -Notation. $T(n)\ge n$ $S(n)\ge \log n$ $O(\cdot)$

Wie auch immer, es ist leicht zu zeigen, dass jede "gewöhnliche" Funktion , die und erfüllt, räumlich konstruierbar ist, aber nicht zeitkonstruierbar. $f$ $f(n)\ge \log n$ $f(n) = o(n)$

Das Konstruierbarkeitsproblem hängt nicht direkt mit einer möglichen Trennung zwischen den Komplexitätsklassen DTIME (f (n)) und SPACE (f (n)) zusammen. Die Aussage der Zeit- und Raumhierarchiesätze beinhaltet jedoch die Konstruierbarkeit. Zum Beispiel:

Zeithierarchiesatz Wenn , zeitkonstruierbare Funktionen sind, die erfüllen , dann ist eine geeignete Teilmenge von . $f$ $g$ $f(n)\log f(n) = o(g(n))$ $\mathbf{DTIME}(f(n))$ $\mathbf{DTIME}(g(n))$

Weitere Informationen finden Sie in Arora & Baraks Buch oder Papadimitriou . (Letzterer verwendet den Begriff "richtige Komplexitätsfunktion", um sich auf eine zu beziehen, die sowohl zeitlich als auch räumlich konstruierbar ist.)

MS Dousti
quelle

Vielen Dank. Ich bevorzuge die Definition, dass eine Funktion zeitlich / räumlich konstruierbar ist, wenn es eine Turing-Maschine gibt, die genau in diesen Schritten / Bandquadraten läuft. Nach den linearen Zeit- / Raumbeschleunigungssätzen entspricht dies natürlich Ihren / Lehrbuchdefinitionen.

Tian Liu

Sadeq, Ihre Definitionen für "Zeit konstruierbar" und "Raum konstruierbar" sind Wort für Wort identisch. Wollen Sie damit sagen, dass dies nur zwei verschiedene Namen für genau dasselbe Konzept sind? Wenn nicht, sollten Sie vielleicht Ihre Definitionen korrigieren.

Yitz

Es ist nur ein Tippfehler.

Tsuyoshi Ito

Entschuldigung Yitz. Ich habe den Tippfehler behoben.

MS Dousti

ist räumlich konstruierbar, aber nicht zeitkonstruierbar. Der Grund ist, dass Sie der binären Darstellung im Raum zuordnen können,jedoch nicht in der Zeit . $f(n)=\log n$ $1^n$ $O(\log n)$ $O(\log n)$

Mohammad Al-Turkistany
quelle

Danke an den Kommentar und die Antwort. Aber können Sie für die Trennung eine Funktion f (n) zeigen, die mindestens linear ist, dh f (n)> = n? Es scheint, dass eine zeitkonstruierbare Funktion aus einem offensichtlichen Grund nicht kleiner als n sein kann: Sie müssen alle Eingabebits lesen, andernfalls kann ein gegnerisches Argument zeigen, dass die Funktion nicht korrekt berechnet wird.

Tian Liu

f (n) = n

$f(n)= n$

f (n) = n + 1

$f(n)=n+1$

$EXP-TIME=EXP-SPACE$ $EXP-SPACE-COMPLETE$ $L\in EXP-SPACE$ $L\subseteq\{0,1\}^*$ $k\in\mathbb{N}$ $L$ $M$ $2^{n^k}$

f (n) = {\begin{cases} 8 n + 2 & if (first ⌊ \sqrt[k]{⌊ \log n ⌋ + 1} ⌋ bits of b i n (n)) \in L \\ 8 n + 1 & else \end{cases}

$f(n)=\left\{\begin{array}{ll} 8n+2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\ 8n+1 & \mbox{else} \end{array} \right.$

$2n$ $f$ $f$ $L$

Diese Antwort verwendet dieselbe Idee.

David G.
quelle