Die räumliche Komplexität der Erkennung von Watson-Crick-Palindromen

Ich habe das folgende algorithmische Problem:

Bestimmen Sie den Raum Turing Komplexität der Erkennung von DNA-Strings, die Watson-Crick-Palindrome sind.

Watson-Crick-Palindrome sind Saiten, deren umgekehrtes Komplement die ursprüngliche Saite ist. Das Komplement ist buchstabenweise definiert, inspiriert von der 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 zwei Möglichkeiten gefunden, dies zu lösen.

Man benötigt Speicherplatz. $\mathcal{O}(n)$

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

Der andere benötigt Speicherplatz. $\mathcal{O}(\log n)$

Beim Lesen der Eingabe. Zählen Sie die Anzahl der Einträge auf dem Eingabeband.
Wenn das Eingabeband fertig gelesen ist
- Kopieren Sie die Ergänzung des Briefes auf das Arbeitsband
- Kopieren Sie den Buchstaben L an das Ende des Arbeitsbandes
(Schleifenpunkt) Wenn der Zähler = 0 ist, löschen Sie das Arbeitsband und schreiben Sie "Ja". Halten Sie dann an
Wenn das Eingabeband L anzeigt
- Bewegen Sie den Eingangskopf um die vom Zähler angegebene Anzahl von Malen nach links (erfordert einen zweiten Zähler).
Wenn das Eingabeband R anzeigt
- Bewegen Sie den Eingangskopf um die vom Zähler angegebene Anzahl von Malen nach rechts (erfordert einen zweiten Zähler).
Wenn die Zelle, die den Wert auf dem Arbeitsband enthält, mit der aktuellen Zelle auf dem Eingabeband übereinstimmt
- Dekrementieren Sie den Zähler um zwei
- Bewegen Sie eine nach links oder rechts, je nachdem, ob sich R oder L auf dem Arbeitsband befindet
- Kopieren Sie das Komplement von L oder R anstelle des aktuellen L oder R auf das Arbeitsband
- Setzen Sie die Schleife fort
Wenn die Werte nicht übereinstimmen, löschen Sie das Arbeitsband und schreiben Sie no. Halten Sie dann an

Dies ergibt ungefähr Speicherplatz zum Speichern beider Zähler, des aktuellen Komplements und des Werts L oder R. $2\log n+2$

Mein Problem

Der erste benötigt sowohl lineare Zeit als auch Raum. Der zweite benötigt Zeit und Speicherplatz. Ich erhielt das Problem aus dem Zitat und kam auf diese beiden Ansätze, aber ich weiß nicht, mit welchem ich gehen soll. Ich muss nur die räumliche Komplexität des Problems angeben. $\frac{n^2}{2}$ $\log n$

Der Grund, warum ich verwirrt bin

Ich würde eher sagen, dass die zweite die beste Option ist, da sie zeitlich besser ist, aber diese Antwort kommt nur von mir, wenn ich Glück habe und einen Algorithmus finde. Es scheint, als würde es kein Glück erfordern, den richtigen Algorithmus zu finden, wenn ich die räumliche Komplexität von etwas angeben möchte. Vermisse ich etwas Sollte ich überhaupt eine Lösung für das Problem finden, um die Komplexität des Raums zu beantworten?

algorithms algorithm-analysis turing-machines space-complexity justausr
quelle

Ich denke, die Frage wäre noch besser, wenn Sie Pseudocode für die Algorithmen geben würden. Schauen Sie hier , um Hilfe zu formatieren.

Raphael

Antworten:

Haftungsausschluss : Der folgende Algorithmus verwendet das Standardmodell nicht für die Komplexität des sublinearen Raums (siehe WP: DSPACE ), da er auf das Eingabeband schreibt. Außerdem befindet sich die Menge der (Watson-Crick) nicht in . Trotzdem ist es eine In-Place-Lösung für viele praktische Zwecke (z. B. wenn jeder Buchstabe in C steht). $\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$ char

Um zu zeigen, dass ein Problem eine bestimmte Raumkomplexität aufweist, muss im Allgemeinen ein Algorithmus entwickelt werden, der diese Raumkomplexität aufweist. Dies erfordert möglicherweise Versuch und Irrtum. Ein besserer Ansatz besteht jedoch darin, das Problem, mit dem Sie sich befassen, gut zu verstehen und über ausreichend Erfahrung mit Algorithmen und Komplexität zu verfügen.

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

Hinweis: Warum zusätzlichen Speicherplatz verwenden, wenn Sie den von der Eingabe belegten Speicherplatz verwenden können?

Tipp: Gehen Sie über die Zeichenfolge hin und her und prüfen Sie jeweils ein Zeichen. Verwenden Sie den Status der Turing-Maschine, um sich zu merken, welches Zeichen Sie überprüfen, und löschen Sie bereits überprüfte Zeichen.

Dave Clarke
quelle

Das macht mein zweiter Algorithmus. Um über eine Zeichenfolge hin und her zu gehen, benötigen Sie Zähler. Für eine Längeneingabe benötigen Sie log n Speicherplatz, um den Zähler zu speichern. Es sei denn, ich habe ein Missverständnis, aber es scheint, als könnten Sie nicht über die Saite hin und her gehen, ohne zu verfolgen, welcher Teil verglichen wurde

justausr

Warum müssen Sie einen Zähler aufbewahren?

Dave Clarke

Wenn ich das Ende der Eingabe erreiche und es 10 Zeichen lang ist. Ich muss 10 Zeichen zurückgehen und speichern, was das letzte Zeichen in der Eingabe war. Sobald ich am Anfang angekommen bin, vergleiche und kopiere ich das zweite Zeichen und gehe 7 Mal nach rechts, um sicherzustellen, dass das zweite Zeichen mit dem 9. übereinstimmt. Woher weiß ich, dass es 7 Mal ist, wenn ich nicht Schritt gehalten habe?

Justausr

Der Kopf kann sich jeweils nur an einer Stelle auf dem Band befinden, aber der Zustand des TM kann sich daran erinnern, was der Kopf gesehen hat, und man kann das Band mit anderen Zeichen markieren, um anzuzeigen, welche Teile des Bandes bereits besucht wurden ( in bestimmten Phasen des Algorithmus).

Dave Clarke

Ich verstehe nicht, was du meinst. Wenn Sie die Zeichen im Eingabestream löschen oder markieren (mit derselben Markierung), können Sie leicht feststellen, wann Sie die Verarbeitung der Eingabezeichenfolge abgeschlossen haben, da Ihnen die Eingabezeichenfolge ausgeht.

Dave Clarke

Die Art und Weise, wie die Frage gestellt wird, sollte eine Obergrenze und eine Untergrenze für die Raumkomplexität ergeben.

Der erste Teil wird normalerweise durchgeführt, indem ein Algorithmus für Ihr Problem vorgestellt wird, aber eine Reduktion auf ein anderes gut untersuchtes Problem würde auch funktionieren (und indirekt auch einen Algorithmus ergeben). Da Sie eine kombinierte Komplexität (Zeit und Raum) nicht berücksichtigen, ist nur der Raum von Bedeutung, selbst wenn die Zeit zunimmt. Sie haben also eine Obergrenze von . $\mathcal{O}(\log n)$

Der zweite Teil ist normalerweise viel kniffliger, aber Sie können leicht zeigen, dass konstanter Platz nicht ausreicht, da dies Ihre Sprache regelmäßig machen würde. Wenn Sie das Pump-Lemma mit beispielsweise , wobei die angenommene ist, reicht dies aus. Dies lässt immer noch eine große Lücke zwischen und . $a^lb^{2l}a^l$ $l$ $\omega(1)$ $\mathcal{O}(\log n)$

Ich habe eine Übung gefunden (siehe Übung 6), die einige Hinweise gibt. Wenn ich ihren Hinweis richtig interpretiere, versuchen Sie zu beweisen, dass es für jede Eingabegröße zu viele verschiedene Äquivalenzklassen der Myhill-Nerode-Beziehung gibt. Dies ähnelt dem Argument, dass Sie nicht mehr als Zeichenfolgen der Länge (wobei Ihr Bandalphabet und Ihre Raumkomplexität ist). Dadurch erhalten Sie eine Untergrenze von . $c\cdot\Gamma^{s(n)}$ $n$ $\Gamma$ $s(n)$ $\Omega(\log n)$

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

frafl
quelle

Es ist sehr wahrscheinlich, dass der klassische Zeit-Raum-Kompromiss für Palindrome auch in Ihrem Fall gilt. Dieses Ergebnis besagt, dass eine Turing-Maschine, die Palindrome im Raum erkennt , Zeit , dh In Ihrem Fall hat der erste Algorithmus und der zweite hat . Man kann auch zeigen, dass die Untergrenze für Leerzeichen . Ich konnte nicht finden, was die beste Obergrenze ist - das heißt, ob es einen Algorithmus gibt, der logarithmischen Raum und Zeit , oder allgemein, für welche Werte von $S$ $\Omega(n^2/S)$

Time \times Space = Ω (n^{2}) .

$\textrm{Time} \times \textrm{Space} = \Omega(n^2).$

T S = Θ (n^{2})

$TS = \Theta(n^2)$

T S = Θ (n^{2} \log n)

$TS = \Theta(n^2\log n)$

Ω (\log n)

$\Omega(\log n)$

O (n^{2} / \log n)

$O(n^2/\log n)$

S

$S$ können wir Zeit . Als Übung können Sie versuchen, andere hybride Algorithmen zu finden, die Ihre beiden Algorithmen interpolieren.

Ω (n^{2} / S)

$\Omega(n^2/S)$

Yuval Filmus
quelle