Wie viel Zeit zum Erkennen von Palindromen im logarithmischen Raum?

20

Es ist bekannt, dass Palindrome auf -Band-Turingmaschinen in linearer Zeit erkannt werden können, nicht jedoch auf Einzelband-Turingmaschinen (in diesem Fall ist die benötigte Zeit quadratisch). Der Linearzeitalgorithmus verwendet eine Kopie der Eingabe und damit auch einen linearen Raum. $2$

Können wir Palindrome in linearer Zeit einer Multitape-Turing-Maschine erkennen, die nur einen logarithmischen Raum verwendet? Welche Art von Raum-Zeit-Kompromiss ist allgemein für Palindrome bekannt?

cc.complexity-theory time-complexity space-complexity space-time-tradeoff Bruno
quelle

22

Unter Verwendung von Kreuzungssequenzen oder Kommunikationskomplexität ist es einfach, den Kompromiss für eine sequentielle Turingmaschine unter Verwendung von Zeit und Raum abzuleiten . $T(n)S(n) = \Omega(n^2)$ $O(T(n))$ $O(S(n))$

Dieses Ergebnis wurde zuerst von Alan Cobham unter Verwendung von Kreuzungssequenzen in der Arbeit Das Erkennungsproblem für die Menge der perfekten Quadrate erhalten, die bei SWAT (später FOCS) 1966 auftrat.

Kristoffer Arnsfelt Hansen
quelle

25

Sie können dasselbe Argument verwenden, um die auf einem einzelnen Band gebundene -Zeit zu beweisen . $\Omega(n^2)$

Angenommen, Sie haben ein TM mit -Raum, das die Palindrome erkennt (wobei ist die Umkehrung von ) in der Zeit . Wenn der (Eingabe-) Kopf die mittlere überschreitet , kann er nur Informationsbits übertragen. Also muss es Kreuze geben, und jede Kreuzung benötigt Mal. $S(n)$ $\{x\,0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ $x^R$ $x$ $T(n)$ $0^{n/3}$ $S(n)$ $\Omega(n / S(n))$ $n/3$

Also ist . $T(n)S(n)=\Omega(n^2)$

Marzio De Biasi
quelle

Ops ... Nachdem ich die Antwort geschrieben hatte, sah ich, dass Kristoffer die Lösung bereits gepostet hatte. Akzeptiert seine Antwort, ich lasse meine nur, weil sie ein paar Details mehr enthält.

Marzio De Biasi

5

Ich denke, es war praktisch gleichzeitig.

Kristoffer Arnsfelt Hansen

Wie Sie vorgeschlagen haben, habe ich Kristoffers Antwort akzeptiert, da er etwas früher war ... Vielen Dank an Sie beide!

Bruno

1

{x 0^{\frac{n}{3}} x^{R} ∣ | x | = | y | = n / 3}

$\{x0^{\frac{n}{3}} x^R \mid |x|=|y|=n/3 \}$ sieht seltsam aus. Besser eine Anmerkung, dass der String-Reverse-Operator ist.

{x 0^{\frac{n}{3}} x^{R} ∣ | x | = n / 3}

$\{x0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$

^{R}

${}^R$

miracle173

2

Zusätzlich zu den anderen Antworten ist es erwähnenswert, dass Palindrome mit O (1) -Raum und O (n) -Zeit erkannt werden können, wenn Randomisierung zulässig ist string und überprüfe, ob die Hashes gleich sind. Es sollte nicht schwierig sein, dies auf einer Turing-Maschine zu tun.

Mobius Knödel
quelle

Wie viel Zeit zum Erkennen von Palindromen im logarithmischen Raum?

Antworten: