Die Raumkomplexität des Erkennens von Watson-Crick Palindromen

Question

Ich habe das folgende algorithmische Problem:

Bestimmen Sie die Komplexität der Raumzunahme des Erkennens von DNA-Strings, die Watson-Crick-Palindrome sind.

Watson-Crick Palindrome sind Saiten, deren umgekehrter Komplement die ursprüngliche Schnur ist. Das ergänzen ist definiert von Buchstaben, inspiriert von DNA: A ist das Komplement von T und C ist das Komplement von G. Ein einfaches Beispiel für ein WC-Palindrom ist ACGT.

Ich habe mir zwei Möglichkeiten ausgedacht, dies zu lösen.

Man erfordert $ mathcal {o} (n) $ space.

• Sobald die Maschine fertig ist, lesen Sie den Eingang. Das Eingabeband muss in umgekehrter Reihenfolge in das Arbeitsband kopiert werden.
• Die Maschine liest dann die Eingabe- und Arbeitsbänder von links und vergleichen jeden Eintrag, um zu überprüfen, ob die Zelle im Arbeitsband das Kompliment der Zelle im Eingang ist. Dies erfordert $ mathcal {o} (n) $ space.

Der andere erfordert $ mathcal {o} ( log n) $ space.

• Beim Lesen der Eingabe. Zählen Sie die Anzahl der Einträge auf dem Eingabeband.
• Wenn das Eingangsband abgelesen wird
  • Kopieren Sie die Ergänzung des Briefes auf das Arbeitsband
  • Kopieren Sie den Buchstaben L zum Ende des Arbeitsbands
• (Schleifenpunkt) Wenn der Zähler = 0, löschen
• Wenn das Eingabeband l liest l
  • Bewegen Sie den Eingangskopf nach links nach links, um die vom Zähler angegebene Male (erfordert einen zweiten Zähler).
• Wenn das Eingabeband R liest r
  • Bewegen Sie den Eingangskopf nach rechts nach der Anzahl der vom Zähler angegebenen Male (erfordert einen zweiten Zähler).
• Wenn die Zelle, die den Wert auf der Arbeitstapel hält
  • Verringern Sie den Zähler um zwei
  • Bewegen
  • Kopieren Sie die Ergänzung von L oder R anstelle des aktuellen l oder r zur Arbeitstape
  • Setzen Sie die Schleife fort
• Wenn Werte nicht übereinstimmen, löschen Sie die Arbeitstapel und schreiben Sie Nein, dann halten Sie es an

Dies ist auf etwa 2 $ log N+2 $ Platz für die Speicherung beider Zähler, das aktuelle Komplement und den Wert L oder R.

Mein Problem

Der erste erfordert sowohl linearer Zeit als auch Platz. Der zweite erfordert $ frac {n^2} {2} $ time und $ log n $ space. Ich bekam das Problem aus dem Zitat und kam mit diesen beiden Ansätzen, aber ich weiß nicht, mit welchen ich gehen soll. Ich muss nur die Raumkomplexität des Problems geben.

Der Grund, warum ich verwirrt bin

Ich würde eher sagen, dass die zweite die beste Option ist, da es in Bezug auf die Zeit besser ist, aber diese Antwort kommt nur von mir, dass ich Glück habe und einen Algorithmus entwickelt habe. Es scheint, als ob ich die Raumkomplexität von etwas geben möchte, würde es kein Glück erfordern, den richtigen Algorithmus zu finden. Vermisse ich etwas? Sollte ich mir sogar eine Lösung für das Problem ausdenken, um die Raumkomplexität zu beantworten?

Answer 1

Haftungsausschluss: Der folgende Algorithmus verwendet das Standardmodell nicht für die Komplexität der Untergräbe (siehe WP: DSPACE), weil es in das Eingabeband schreibt. Darüber hinaus ist der Satz von (Watson-Crick) Palindromen nicht in $ mathsf {dspace} ( mathcal {o} (1)) = mathsf {reg} $. Trotzdem handelt es sich für viele praktische Zwecke an (z. B. wenn jeder Buchstabe a ist char in c).

Um zu zeigen, dass ein Problem eine bestimmte Raumkomplexität hat, muss man im Allgemeinen einen Algorithmus entwickeln, der diese Raumkomplexität hat. Dies kann Versuch und Irrtum erfordern, aber ein besserer Ansatz ist es, das Problem, das Sie zu sehen, und viel Erfahrung in Algorithmen und Komplexität ein gutes Verständnis zu haben.

Für dieses spezielle Beispiel gibt es einen dritten Algorithmus, der keinen zusätzlichen Platz benötigt und $ o (n^2) $ Zeitkomplexität erfordert. Dieser Algorithmus wäre ein konstanter Raum.

Hinweis: Warum zusätzlichen Platz nutzen, wenn Sie den von der Eingabe besetzten Raum nutzen können?

Hinweis: ZIP-Hin- und Her über die Zeichenfolge überprüft jeweils ein Zeichen-Verwenden Sie den Status der Turing-Maschine, um sich zu erinnern, welches Zeichen Sie überprüft und löschen, die Sie bereits überprüft haben.

Answer 2

Die Art und Weise, wie die Frage gestellt wird, sollten Sie sich eine einfallen lassen obere Grenze und ein Untergrenze auf der Raumkomplexität.

Der erste Teil wird normalerweise durchgeführt, indem ein Algorithmus für Ihr Problem vorgestellt wird, aber eine Reduzierung zu Einige andere gut untersuchte Problemen würden ebenfalls funktionieren (und indirekt einen Algorithmus ergeben). Da Sie keine kombinierte Komplexität (Zeit und Raum) betrachten, nur der Raum ist, auch wenn die Zeit zunimmt. Sie haben also eine Obergrenze von $ mathcal {o} ( log n) $ gefunden.

Der zweite Teil ist normalerweise viel schwieriger, aber Sie können leicht zeigen, dass ständiger Raum nicht ausreicht, da dies Ihre Sprache regelmäßig macht. Verwenden Sie das Pumping Lemma mit, sagen wir $ a^lb^{2l} a^l $, wobei $ l $ die angenommene Pumpennummer ist, wird den Trick machen. Dies hinterlässt immer noch eine große Lücke zwischen $ Omega (1) $ und $ mathcal {o} ( log n) $.

Ich fand eine Übung (Siehe Übung 6) Das gibt einige Hinweise. Wenn ich ihren Hinweis richtig interpretiere, versuchen Sie zu beweisen, dass es für jede Eingangsgröße zu vielen verschiedenen Äquivalenzklassen der Myhill-Nerode-Beziehung gibt. Dies ähnelt dem Argument, dass Sie nicht mehr als $ C cdot gamma^{s (n)} $ Strings mit Länge $ n $ (wobei $ gamma $ Ihr Band Alphabet und $ S (n) ist, nicht unterscheiden können. $ Ihre Raumkomplexität). Dadurch erhalten Sie eine untere Grenze von $ Omega ( log n) $.

---

Beachten Sie, dass Sie sich nicht um die Ergänzung der Buchstaben kümmern müssen, da diese Operation trivial ist. Alles, was für gewöhnliche Palindrome funktioniert, kann mit ein paar weiteren Zuständen geändert werden, um Ihr Problem zu lösen.

Answer 3

Es ist sehr wahrscheinlich, dass die Klassiker Zeitraum-Kompromiss für Palindrome hält auch in Ihrem Fall. Dieses Ergebnis besagt, dass eine Turing -Maschine, die Palindrome im Raum $ s $ erkennt 2). $$ in Ihrem Fall hat der erste Algorithmus $ ts = theta (n^2) $ und der zweite $ ts = theta (n^2 log n) $. Man kann auch zeigen, dass die Untergrenze für den Raum $ omega ( log n) $ ist. Ich konnte nicht gefunden, was die beste Obergrenze ist - das heißt, ob es einen Algorithmus mit logarithmischem Raum und Zeit $ O (n^2/ log n) $ oder im Allgemeinen für welche Werte von $ gibt S $ können wir Zeit erreichen $ Omega (n^2/s) $. Als Übung können Sie versuchen, andere, Hybridalgorithmen zu finden, die Ihre beiden Algorithmen interpolieren.