Große Lücken zwischen RAM und Turing-Maschinenkomplexität

Wenn wir nur Probleme in P betrachten, gibt es große Lücken zwischen dem schnellsten bekannten Wort-RAM-Algorithmus und dem schnellsten bekannten Turing-Maschinenalgorithmus für bestimmte Probleme? Ich bin besonders interessiert, wenn es große Lücken für natürliche Probleme von allgemeinem Interesse gibt.

Es ist bekannt, dass jedes Problem, das Sie auf einer RAM-Maschine in der Zeit berechnen können, in einer Turing-Maschine höchstens in der Zeit T ( n ) 2 auftreten kann . Sie müssen beachten, dass die Gesamtgröße des verwendeten Speichers nicht mehr als T ( n ) betragen kann , da dies bedeuten würde, dass Sie mehr Schreibvorgänge als T ( n ) ausgeführt haben. Jedes Mal, wenn Sie etwas aus dem RAM-Speicher abrufen, wird das Turing ausgeführt Maschine würde im schlimmsten Fall T ( n $T(n)$$T(n)^2$$T(n)$$T(n)$$T(n)$Zeit, um das gewünschte Element nacheinander vom Band zu finden. Neben dem Speicherzugriff sollten die restlichen Vorgänge ungefähr dieselbe Zeit in Anspruch nehmen. Und so bekommen Sie die Grenze.

Das folgende Beispiel zeigt, dass ein Algorithmus , der O ( n log ( n ) ) benötigt , um ein Problem mit Word-Ram zu lösen, möglicherweise O ( n 2 log ( n ) 3 ) auf einer 1-Band-Turing-Maschine (TM) benötigt, die genau ausgeführt wird alle durch A angegebenen Berechnungen . Ich verstehe, dass sich die Frage auf das 1-Band-TM bezieht, und ich verwende dieses nur in meiner Antwort. Dies ist eine Bearbeitung, um die Bemerkungen von Emil Jeřábek anzusprechen.$A$$O(n\log(n))$$O(n^2 \log(n)^3)$$A$

Wir werden die folgende allgemeinere Schlussfolgerung finden . Um zu beweisen, dass das TM in ein in O ( T ( n ) ) durch einen Algorithmus A im RAM gelöstes Problem lösen kann , reicht es nicht aus, A auf dem TM auszuführen . Möglicherweise ist ein cleverer Algorithmus erforderlich. Gleiches gilt, wenn man ein O beweisen will ( n log ( n ) $O(T(n)^2)$$O(T(n))$$A$$A$$O(n\log(n))$Overhead. Die Existenz eines cleveren Algorithmus zu beweisen, wann immer dies erforderlich ist, scheint, gelinde gesagt, alles andere als unmittelbar zu sein. Dies steht nicht im Einklang mit anderen Antworten, die grundsätzlich nur vorschlagen, auf dem TM alle RAM-Berechnungen (von Algorithmus ) zu simulieren / auszuführen , um eine TM-Komplexität wie O ( T ( n ) 2 ) oder O ( T ( n ) n log ) anzukündigen ( n ) ) .$A$$O(T(n)^2)$$O(T(n)n\log(n))$

Problem: Wir erhalten eine Array / Tabelle mit n = 2 k Ganzzahlen, die jeweils in log ( n ) Bits gespeichert sind . Wir erhalten ein zweites Array d mit log ( n ) -Positionen, von denen jedes eine Anzahl von log ( n ) -Bits aufzeichnet . Für jedes t ∈ [ 0 .. log ( n ) - 1 ] definieren wir X t = 1, wenn tab [ i $\texttt{tab}$$n=2k$$\log(n)$$\texttt{d}$$\log(n)$$\log(n)$$t\in[0..\log(n)-1]$$X_t=1$$\texttt{tab}[i]$MOD MOD d [ t ] ∀ i ∈ [ 0 .. n / 2 - 1 ] . Ansonsten ist X t = 0 . Ausgabe ∑ log ( n ) - 1 t = 0 X t . Ich betrachte die Eingabe als Band mit n log ( n ) $\texttt{d}[t]=\texttt{tab}[n/2+i]$$\texttt{d}[t]~\forall i\in [0..n/2-1]$$X_t=0$$\sum_{t=0}^{\log(n)-1} X_t$ Binärziffern, um die Kommentare von Emil Jeřábek anzusprechen.$n\log(n)+\log(n)\log(n)$

Algorithmus im RAM$A$ Ein RAM mit der Wortgröße benötigt O ( n log ( n ) + log ( n ) 2 ) = O ( n log ( n ) ) , um die Eingangsdaten der Binärzeichenfolge zu lesen. Nach dem Lesen der Daten kann es jedoch nur mit Wörtern der Größe log ( n ) arbeiten . Algorithmus A berechnet jedes X t in O ( $w=\log(n)$$O(n\log(n)+\log(n)^2)$$O(n\log(n))$$\log(n)$$A$$X_t$ indem Sie alle i ∈ [ 0 .. n / 2 - 1 ] durchlaufenund die Bedingung testen. Die Hauptschleife von A istFOR t = 0 , 1 , 2 , … log ( n ) - 1 : Berechne X t . Die Gesamtkomplexität ist O ( n log ( n ) ) (Lesen von Daten) + O ( n log ( n ) $O(n)$$i\in [0..n/2-1]$$A$$t=0, 1, 2, \dots \log(n)-1$$X_t$$O(n\log(n))$$O(n\log(n))$(führt die Berechnungen durch), damit alles in O ( n log ( n ) ) im RAM erledigen kann .$A$$O(n\log(n))$

Algorithmus auf dem 1-Band-TM:$A$ Ich behaupte, das Ein-Band-TM benötigt Zeit für ein festes t . Aus Sicht des TM entspricht die Bestimmung von A t dem Testen der Gleichheit von zwei binären Zeichenfolgen der Länge O ( n log ( n ) ) . Beispielsweise kann die Registerkarte MOD-Operation [ i ] MOD d [ t ] dem Entfernen von Bit 0 der $O(n^2 \log(n)^2)$$t$$A_t$$O(n\log(n))$$\texttt{tab}[i]$$\texttt{d}[t]$$0$ . In solchen Fällen entspricht die Bestimmung von A t der Gleichheitsprüfung an Bitfolgen mit der Länge n ( log ( n ) - 1 ) / 2 . Es ist bekannt, dass zum Testen der Gleichheit von zwei Zeichenfolgen der Länge m O ( m 2 ) auf dem 1-Band TMerforderlich ist, aber ich kann momentan keine Referenz finden. Ich gebe jedoch einen Beweis in ps. Wenn das TM dieHauptschleifevon A ausführt, muss es mindestens O ( ( n log n) ausgeben$\texttt{tab}[i]$$A_t$$n(\log(n)-1)/2$$m$$O(m^2)$$A$ für jedes t = 0 , 1 , 2 , … log ( n ) - 1 , was zu O ( n 2 log ( n ) 3 ) führt .$O((n\log n)^2)$$t=0, 1, 2, \dots \log(n)-1$$O(n^2 \log(n)^3)$

ps. Ich zeige, dass Gleichheitstests an Bitfolgen mit Bits nicht schneller sein können als Palyndromtests an Zeichenfolgen mit m Bits (Palyndrom dauert bekanntermaßen mindestens O ( m 2 ) Zeit). Wir können jeden TM-Algorithmus für Gleichheitstests modifizieren, um das Palindrom zu lösen. Angenommen, das Gleichheitstest-TM beginnt mit zwei Ganzzahlen: eine links vom Kopf und eine rechts (dies ist die einfachste Eingabeform für das TM). Jede Bewegung über die linken Positionen kann über die rechten Positionen gespiegelt (reflektiert) werden. Wir bauen ein gespiegeltes TM: Immer wenn sich das anfängliche TM an einer Position befindet - x < 0 (links), befindet sich das gespiegelte TM an Position $m$$m$$O(m^2)$$-x<0$$x$(zur Rechten). Wenn ein TM Gleichheitstests in weniger als lösen würde, würde dieses modifizierte gespiegelte TM Palindrom in weniger als O ( m 2 ) lösen .$O(m^2)$$O(m^2)$

Es gibt auch einige TM-Algorithmen, die Gleichheitstests durchführen, und alle erfordern eine quadratische Zeit, da sie im Zickzack ausgeführt werden müssen. Siehe beispielsweise das Beispiel 2 der Turing-Maschine unter Kursen.cs.washington.edu/courses/cse431/14sp/scribes/ lec3.pdf