Warum lehnen wir Turingmaschinen ab, die weniger Platz als das Protokoll der Länge der Eingabe benötigen?

8

In Computational Complexity: Modern Approach von Arora und Barak wird dies erwähnt

Wir benötigen jedoch da das Arbeitsband die Länge , und wir möchten, dass sich die Maschine zumindest den Index der Zelle des aktuell gelesenen Eingabebandes merken kann.S(n)>log⁡nn

Was bedeutet das genau ? Ich verstehe den Punkt nicht. Was bedeutet " Erinnern an den Index der Zelle, die gerade vom Kopf des Eingabebandes gelesen wird"? Irgendwelche Klarstellungen?

Beachten Sie, dass wir die Bewegungen des Eingabebandes nicht in unsere Platzüberlegungen einbeziehen, sodass wir nur für das Arbeitsband zählen

complexity-theory turing-machines space-complexity Fawzy Hegab
quelle
1
Arora hat einen Mitautor.
Yuval Filmus
@ YuvalFilmus, das habe ich behoben. Vielen Dank.
Fawzy Hegab

Antworten:

6

Betrachten Sie jedes Programm in einer höheren Sprache, bei dem eine Schleife über alle Elemente verläuft:

for i from 1 to n
    do something
end for

Diese Schleife Implementierung nimmt Arbeitsbereich, da die Variable nimmt Bits zu speichern. Wenn Sie nicht einmal so viel Speicher verwenden dürfen, müssen Sie bei der Implementierung eines nicht trivialen Algorithmus sehr vorsichtig sein, wenn dies überhaupt möglich ist. Beispielsweise hängen alle Ergebnisse stark von der genauen Definition des Berechnungsmodells ab.O(log⁡n)iO(log⁡n)

Arora und Barak wollen sich nicht auf solche Themen konzentrieren, also gehen sie einfach davon aus, dass Sie mindestens logarithmischen Raum erhalten. Es gibt genug interessante Dinge zu sagen, ohne sich Sorgen machen zu müssen, ob im sublogarithmischen Raum eine allgemeine Reduktion durchgeführt werden kann. (Und wenn Sie reguläre Sprachen lernen möchten - Sprachen, die mit konstantem Raum erkannt werden können -, brauchen Sie keine Komplexitätstheorie.)

Yuval Filmus
quelle
Die Motivation ist also, dass wir nur TMs untersuchen, die durch Kompilierung von RAM-Modellprogrammen erhalten wurden? Da es viele Sprachen gibt, kann ein TM ohne zusätzlichen Speicher entscheiden.
Raphael
@Raphael Nein, wir möchten uns nur nicht auf Fälle konzentrieren, in denen die genaue Definition des Modells sehr wichtig sein könnte. Es gibt genug interessante Dinge zu sagen, ohne sich Sorgen machen zu müssen, ob im sublogarithmischen Raum eine allgemeine Reduktion durchgeführt werden kann.
Yuval Filmus
2
Wenn Sie reguläre Sprachen lernen möchten, benötigen Sie keine Komplexitätstheorie.
Yuval Filmus