Satz Falls B in L und A log-raum reduzierbar auf B dann A in L

Einfache Sprache

Def. Satz Falls B in L und A log-raum reduzierbar auf B dann A in L

Aus $A\leq_\mathrm{L} B$ und $B\in\mathbf L$ folgt $A\in\mathbf L$.

Beweis Idee: Das Ausgabeband von der Log-Raum Reduktion ist das Eingabeband von der TM ist, die B löst. Damit gehört es gedanklich zur zum Arbeitsband, der daraus entstehenden TM und unterliegt der Logarithmischen Platzkomplexität. Nun kann aber die Ausgabe der Log-Raum Reduktion mehr als Logarithmischen Platz brauchen. Der Trick is nun die Ausgabe der Reduktion nur für ein bestimmtes Zeichen zu berechnen. Jeweils das Zeichen was gerade von der TM die B entscheidet gebraucht wird. Dadurch muss nur noch das jeweilige Zeichen gespeichert werden, aber dafür für jedes Zeichen die Reduktion wiederholt werden. Es wird also Zeit gegen Platz getauscht.

Beweis: Sei $\mathcal M_B$ die TM die $B$ in L entscheidet und $f$ die Log-Raum-Reduktion von $A$ auf $B$. Dann funktioniert die TM $M_A$ die $A$ in L entscheidet wie folgt: $\mathcal M_A$ merkt sich an welche Stelle der Lese-Kopf von $\mathcal M_B$ auf der Eingabe $f(w)$ zeigt. Möchte $\mathcal M_B$ nun das Zeichen an einer bestimmten Stelle in der Eingabe lesen, lässt $\mathcal M_A$ die Reduktion $f$ auf $w$ erneut laufen. Es werden alle Zeichen bis zu der gefragten Stelle verworfen, und bei der gefragten Stelle wird gestoppt und das Zeichen an $\mathcal M_B$ weitergereicht. Die berechnet daraus die Folgekonfiguration und dann geht das wieder von vorne los, bis $\mathcal M_B$ akzeptiert oder verwirft, was dann von $\mathcal M_A$ so weitergegeben wird.

Bemerke: das dafür Teile von $f(w)$ mehrmals berechnet werden müssen. Es ist also bzgl. der Zeitkomplexität ineffizient. Aber bzgl der Platzkomplexität werden jeweils nur der Platz für die Arbeitsbänder beider TMs und das Zeichen von $f(w)$ was “on the fly” berechnet wurde.