[Komplexitätstheorie] DSPACE Beispiel

09.03.2023, 15:58

Malcang

[Komplexitätstheorie] DSPACE Beispiel

Hallo zusammen,

diesmal was komplexitätstheoretisches Augenzwinkern

Ich tue mir sehr schwer, da den Zugang zu finden. Wir haben definiert:
$\begin{eqnarray*} M \end{eqnarray*}$ ist eine Turingmaschine, L(M) die erzeugte Sprache und $\begin{eqnarray*} f: \mathbb N \rightarrow \mathbb N \end{eqnarray*}$ , eine monoton wachsende Funktion. Dann ist (unter anderem)

Zitat:

DSPACE(f) := $\begin{eqnarray*} \{L(M) | \text{ M deterministisch & f-platzbeschränkt}\} \end{eqnarray*}$

Als Beispiel ist angegeben:
$\begin{eqnarray*} \{a^nb^nc^n|n\geq 1\}\in DSPACE(\log(n)) \end{eqnarray*}$ .

Wie würde ich rausfinden, dass diese Menge in DSPACE(log(n)) liegt?
Muss ich da so interpretieren, dass $\begin{eqnarray*} \{a^nb^nc^n|n\geq 1\} \end{eqnarray*}$ von einer deterministischen Turingmaschine erzeugt wird, die $\begin{eqnarray*} \log(n) \end{eqnarray*}$ -platzbeschränkt ist?
Und $\begin{eqnarray*} \log(n)- \end{eqnarray*}$ platzbeschränkt heißt ja, dass die Turingmaschine beim Eingabewort $\begin{eqnarray*} w \end{eqnarray*}$ höchstens den Platzbedarf $\begin{eqnarray*} \log(|w|) \end{eqnarray*}$ hat.
Wenn nun $\begin{eqnarray*} w = a^nb^nc^n \end{eqnarray*}$ mein Eingabewort ist, dann sollte die Turingmaschine also Platzbedarf höchstens $\begin{eqnarray*} \log(3n) \end{eqnarray*}$ haben? Sehe ich das richtig?
Und muss ich diese Turingmaschine angeben, um zu entscheiden, ob die Menge in DSPACE liegt?

Edit: Mir kommt da gerade eine Idee.
Ich könnte doch eine Maschine mit einem Eingabeband und 3 Schreibbändern anlegen. Dann schreibe ich die Anzahl der a in Binärdarstellung auf das erste Band, die der b auf das zweite, die der c auf das dritte.
Das geht soweit ich weiß in log(n)-Platz.
Nun nur noch vergleichen, dass benötigt gar keinen Platz.

Edit2:
Ich glaube ich hab's. Ich lege eine TM mit Eingabeband und drei Arbeitsbändern an. Nun schreibe ich unter das erste a eine 1 auf das erste Arbeitsband. Dann unter das erste b eine 1 auf das zweite und unter der erste c eine 1 auf das dritte Arbeitsband.
Nun gehe ich von vorne wieder durch und schiebe die 1en jeweils eins nach rechts indem ich prüfe, ob der jeweils nächste Buchstabe nochmal da ist.
Wenn ich eine 1 verschiebe, müssen auch die anderen beiden verschoben werden.
Ist etwas umständlich ausgedrückt, sorry.
Aber das müsste dann also eine TM mit Platzbedarf 1 sein? Stimmt das?

Neue Frage »

Antworten »

[Komplexitätstheorie] DSPACE Beispiel

Verwandte Themen