Simulieren Sie die Verkettung von zwei Log-Space-Programmen im Log-Space

Ich habe zwei log-Raumfahrtprogramme bekommt und .$F$$G$

• Programm wird in das Array eingegeben$F$$A[1..n]$ und erstellt das Ausgabearray $B[1..n]$.
• Programm $G$ wird als Eingabe erhalten $B$ wie erstellt von $F$ und erstellen Sie daraus das Ausgabearray $C[1..n]$.

Ich muss einen Beweis schreiben, dass es ein Log-Space-Programm gibt $H$, die Eingabe Array erhalten $A$ und erstellen Sie daraus ein entsprechendes Array $C$. Aber ich kann nicht den richtigen Weg finden, es zu schreiben. Wie wird das gemacht?

Ein Log-Space-Programm ist ein Programm, das verwendet $O(\log n)$Speicherbits. Hier sind einige Bedingungen, die Sie einhalten müssen:

1. Sie müssen nur Variablen verwenden, die einen einfachen Ganzzahltyp haben (z. B. intin C ++, longintin Pascal).

2. Der zulässige Bereich der Ganzzahl ist definiert: if $n$ ist die Größe der Eingabe, die wir in Variablen speichern können, nur Werte, die polymonial sind $n$.

   Zum Beispiel: Wir können Variablen haben, die Werte annehmen können $[-n...n]$, $[-3n^5...3n^5]$ oder auch Werte $[-4...7]$, aber wir können keine Variablen haben, die Werte annehmen $[ 0...2^n]$. Es sind keine anderen Variablentypen zulässig, auch keine Arrays und Iteratoren.

3. Ausnahmen von den Regeln sind Eingabe und Ausgabe. Die Eingabe ist in speziellen Variablen (meistens Arrays) verfügbar, aus denen Ihr Programm nur lesen kann, und die Ausgabe kann nur in andere spezielle Variablen geschrieben werden. Sie können also nicht aus der Ausgabe lesen und die Werte von Eingabevariablen usw. nicht erhöhen.

4. Ihre Programme können keine Rekursion verwenden.

Beispiel eines in Pascal geschriebenen Protokollspeicherprogramms (damit jeder es verstehen kann), das die größte Zahl im Array der Ganzzahl findet

    var n: integer;  //input variable the number of elements in A
    A: array [1..n] of integer; //input variable - the array of integers
    m: integer;      // output variable, the position of maximum
    i, j: integer;   //working variables
    begin
      j := 1;
      for i := 2 to n do
        if A[i] > A[j] then j := i;
      m := j;
    end;

Die einzigen zwei Variablen hier sind jund iund sie nehmen offensichtlich Werte in an$[1...n]$. Damit sind alle Bedingungen erfüllt und es handelt sich wirklich um ein Log-Space-Programm.

Die Idee hier ist, dass wir die Ausgabe des ersten Algorithmus nicht vollständig berechnen können, da er mehr als logarithmischen Raum beanspruchen kann (er kann polynomiell groß sein). Aber wir müssen nicht, wenn wir intelligent sind. Was wir tun können, ist den zweiten Algorithmus zu simulieren und die benötigten Bits aus der Ausgabe des ersten Algorithmus online zu erzeugen. Mit anderen Worten, wir simulieren die zweite Maschine, wenn sie Bit lesen möchte$i$ von seiner Eingabe, dh das Bit $i$ Von der Ausgabe der ersten Maschine stoppen wir die Simulation der zweiten Maschine, simulieren die erste und zählen (aber speichern nicht) die ausgegebenen Bits, bis sie die ausgeben $i$Zu diesem Zeitpunkt können wir die Simulation der ersten Maschine stoppen und mit der Simulation der zweiten Maschine fortfahren, da wir jetzt den Wert dessen haben, was sie lesen wollte.