Konfigurationsgraphen

Configuration Graphen sind ein theoretisches Werkzeug in Komplexitätstheorie verwendet werden, um eine Beziehung zwischen Graphen Erreichbarkeit und Komplexitätsklassen zu beweisen.

Definition

Ein theoretisches Rechenmodell, wie Turing-Maschine oder endliche Automaten, erläutert, wie eine Berechnung zu tun. Das Modell erklärt sowohl, was eine anfängliche Konfiguration der Maschine und die können Schritte unternommen werden, um die Berechnung fortgesetzt werden, bis wir schließlich stoppen. Eine Konfiguration, die auch als ein momentaner Beschreibung ist eine endliche Darstellung der Maschine zu einem bestimmten Zeitpunkt. Zum Beispiel für einen endlichen Automaten und eine Eingabe, die Konfiguration wird der aktuelle Zustand und der Anzahl der gelesenen Briefen für Turingmaschine wird es der Zustand ist, der Inhalt des Bandes und die Position des Kopfes sein. Ein Konfigurationsgraph ist ein gerichteter Graph markiert, wo das Etikett der Eckpunkte sind die möglichen Konfigurationen der Modelle und wo es eine Kante von einer Konfiguration zu einer anderen, wenn es an einen Rechenschritt des Modells entsprechen.

Die anfängliche Annahme und Konfiguration der Maschine sind spezielle Eckpunkte des Konfigurationsgraphen. Die Berechnung nimmt, wenn und nur wenn es einen Pfad von einem Anfangspunkt zu einem akzeptierenden Scheitel.

Nützliche Eigenschaft

Wenn die Berechnung deterministisch ist dann von einer beliebigen Konfiguration gibt es höchstens einen möglichen Schritt, dass die Grafik des Ausgangsgrad 1 ist, und gibt es genau einen Ausgangszustand zurück.

Sobald wir fügen Sie ein Dummy-Anfangspunkt mit einer Kante zu jedem Anfangsecke und einem Dummy akzeptieren Scheitelpunkt mit einer Kante von jeder Annahme von Vertex, die Überprüfung, ob es eine akzeptierende Berechnung benötigt nur zu prüfen, ob es einen Weg von der ersten Scheitelpunkt an den übernehm Vertex, die die Erreichbarkeit Problem.

Ein Zyklus im Graphen bedeutet, dass es eine Möglichkeit der Endlosschleife in der Berechnung.

Größe des Diagramms

Die Berechnungsgraphen kann unendlich groß sein, wenn es keine Beschränkungen der möglichen Konfigurationen; ja, es ist leicht zu sehen, dass es Turingmaschinen, die beliebig großen Konfigurationen erreichen können.

Es ist auch möglich, um endliche Graphen haben: auf deterministischer endlicher Automat mit den Staaten, für ein gegebenes Wort von der Größe der Konfiguration der Position des Kopfes und den aktuellen Stand zusammen. Sodass die Grafik von der Größe und dem zugänglichen Teil von der intitial Staat ist von der Größe.

Die Nutzung dieser Aufgabe

Dieser Begriff ist nützlich, weil es Berechnungsprobleme reduziert, um Erreichbarkeitsproblemen grafisch darzustellen.

Da beispielsweise die Erreichbarkeit ist in NL, als wir können Konfigurationen im Raum, logarithmische in der Größe des eingespeist wird, und da die Konfiguration des Turingmaschine in NL ist in der Tat der logarithmischen Größe darstellen, dann ist ein Graph-Erreichbarkeits komplette für NL.

In der anderen Richtung, hilft es, die Komplexität eines Berechnungsmodells zu überprüfen; das Entscheidungsproblem für ein Modell, dessen Konfiguration sind der Raum, der in der logarithmischen Größe der Eingabe ist, ist in der NL. Dies ist beispielsweise der Fall von endlichen Automaten und endliche Automaten mit einem Zähler.

  0   0
Vorherige Artikel Fairgrounds Square Mall
Nächster Artikel Andhra Patrika

Kommentare - 0

Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha