{"id":1471,"date":"2013-05-04T10:51:35","date_gmt":"2013-05-04T08:51:35","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1471"},"modified":"2025-11-25T23:08:17","modified_gmt":"2025-11-25T22:08:17","slug":"tib-nichtsdeterministische-komplexitat-lernziele-ke3","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1471","title":{"rendered":"TIB: Nichtsdeterministische Komplexit\u00e4t (Lernziele KE3, Update 3)"},"content":{"rendered":"

Update<\/strong>: durch den Hinweis von Philipp ist mir noch etwas aufgefallen. Der Vergleich von deterministischen Turingmaschinen zu nichtdeterministischen ist nicht ganz deutlich r\u00fcber gekommen. Daher habe ich den Abschnitt noch einmal \u00fcberarbeitet (Lernziel 2, 3 und 4).<\/p>\n

Update<\/strong>: Antworten zu den Lernzielen.<\/p>\n

Das ist ein sch\u00f6nes Thema. Wirklich. Auch keinerlei Sarkasmus hier drin versteckt. Ich m\u00f6chte – wie im Skript auch – zun\u00e4chst den Nichtdeterminismus anhand eines klassischen Problems erl\u00e4utern:<\/p>\n

Hamiltonkreisproblem<\/strong><\/p>\n

Zun\u00e4chst: was ist ein Hamiltonkreis? Ein Hamiltonkreis ist ein Weg in einem Graphen, der jeden Knoten genau 1x enth\u00e4lt. Es ist ein Problem aus der Graphentheorie. Ich klaue mir wieder ein Bild aus der zugeh\u00f6rigen Wikipedia-Seite um das zu verdeutlichen:<\/p>\n

\"hamilton\"<\/a><\/p>\n

Quelle: Wikipedia <\/a><\/p>\n

Das Problem ist es diesen Weg in so einem Graphen zu finden (sinniger Weise ist einer schon im Bild eingezeichnet). Problem? Wir k\u00f6nnten alle Wege durchprobieren. Jeden Knoten mal durchtesten. Das Problem hierbei ist jedoch, dass der Aufwand exponentiell ist (in Abh\u00e4ngigkeit von der Anzahl der Knoten). Was wir brauchen ist jedoch ein effizienter Algorithmus.<\/p>\n

Hier kommt unser Nichtdeterminismus ins Spiel, denn uns interessieren ja vielleicht nicht alle<\/strong> Hamiltonkreise im Graphen, sondern einfach nur ob es einen gibt. Was w\u00e4re dann der Ansatz? Raten und Pr\u00fcfen! Wir raten eine Knotenfolge und pr\u00fcfen ob sie uns in einem Hamiltonkreis bringt. Und das geht in Polynomialzeit mittels einer nichtdeterministischen TM, einer \\(NTM\\).<\/p>\n

Lernziel 1<\/h2>\n

Erkl\u00e4rung der Modelle der KTM und der NTM<\/em><\/p>\n

Die Kontrollturingmaschine<\/strong> (KTM)<\/strong> aus dem Skript tut nichts weiter als das zu pr\u00fcfen. Es bekommt zwei Eingaben, n\u00e4mlich \\(x\\) (auf dem Eingabeband) und \\(y\\) (auf Band 0, was als Ausgabeband ausgezeichnet ist, aber nicht ben\u00f6tigt wird), wobei \\(y\\) ein Beweis daf\u00fcr sein soll, dass \\(x\\in{L}\\). H\u00e4lt die Maschine also in dem ausgezeichneten Endzustand \\(q_{+}\\), so ist \\(y\\) ein Beweis, dass \\(x\\in{L}\\). Wir m\u00fcssen hier aber jedes Mal das \\(y\\) (z.B. die zu testende Knotensequenz) auf Band 0 schreiben.<\/p>\n

Wir k\u00f6nnen das \\(y\\) aber auch raten lassen. Hierf\u00fcr ist unsere nichtdeterministische Turingmaschine<\/strong> (NTM)<\/strong> da. Statt einer \u00dcbergangsfunktion (bei einem entsprechenden Zustand und einem entsprechenden Zeichen unter dem Lesekopf wird spezifiziert was unter den Lesekopf geschrieben, in welche Richtung sich bewegt und welcher Zustand als n\u00e4chstes eingenommen werden soll) wird hier eine \u00dcbergangsrelation (es gibt mehrere \u00dcberg\u00e4nge, die zuf\u00e4llig ausgef\u00fchrt werden) verwendet. Jetzt zieht Ihr die Augenbrauen zusammen, richtig? Das liegt daran, dass dieses Modell kein Modell ist, welches man real implementieren kann: es ist rein theoretischer Natur. L\u00f6st euch also etwas von eurer „Hardware“ \ud83d\ude09 Wenn man also irgendwelche Abzweigungen nimmt und am Ende in einem der Endzust\u00e4nde landet, so ist \\(x\\in{L}\\). Es z\u00e4hlt also einfach nur, dass es einen Weg, der die Maschine in einen Endzustand f\u00fchrt gibt wenn \\(x\\in{L}\\) ist.<\/p>\n

Durch die Verzweigungen bilden die Berechnungen am Ende einen Baum, dessen Rechenzeit \\(t_M\\) die Tiefe des Baums darstellt. Der Bandbedarf \\(s_M\\) ist das Maximum des Bandbedarfs aller Knoten in diesem Baum.<\/p>\n

Antwort zum Lernziel<\/strong>: mit der Kontrolltunringmaschine (KTM) pr\u00fcfen wir eine vorgegebene L\u00f6sung auf ihre Richtigkeit. Die vorgegebene L\u00f6sung wird Hilfseingabe genannt und muss immer manuell eingegeben werden.<\/p>\n

Mittels nichtdeterministischer Turingmaschine (NTM) k\u00f6nnen wir diese Hilfseingabe auch raten lassen: dabei bekommt die NTM eine \u00dcbergangsrelation, die nicht eindeutig ist. Bei einer Belegung und einem Zustand kann kann es also mehrere Folgezust\u00e4nde geben, so dass eine zuf\u00e4llige Auswahl erfolgt (oder alle m\u00f6glichen Pfade parallel durchlaufen werden).<\/p>\n

Lernziel 2<\/h2>\n

\u00c4quivalenz der Modelle begr\u00fcnden<\/em><\/p>\n

Spannend ist, dass beide Modelle (KTM und NTM) \u00e4quivalent sind. Vor allem, dass man sie gegenseitig innerhalb der gleichen Zeit- und Bandschranken ineinander \u00fcberf\u00fchren kann. Die \u00dcberf\u00fchrung einer KTM in eine NTM geschieht zun\u00e4chst wie folgt:<\/p>\n

KTM nach neue KTM mit Hilfsalphabet \\(\\{0,1\\}\\)<\/strong><\/p>\n

 1. die KTM wird in eine neue KTM mit dem Alphabet \\(\\{0,1\\}^m\\) \u00fcberf\u00fchrt (\\(2^m\\) wenn die Anzahl der Zeichen nicht bereits eine Zweierpotenz darstellt)<\/p>\n

2. die Befehle der alten KTM werden durch Befehlsfolgen ersetzt, wo der Befehl \\(m\\) aufgerufen wird. Ebenso ergeht es den Tests<\/p>\n

Die Laufzeit erh\u00f6ht sich hier nur um einen konstanten Faktor. Und da dieser uns bei der Betrachtung der Schranke nicht interessiert, bleiben wir innerhalb der Laufzeit der alten KTM. Ebenso beim Bandbedarf.<\/p>\n

Neue KTM nach NTM<\/strong><\/p>\n

Nun erzeugen wir aus der neuen KTM mit Hilfsalphabet \\(\\{0,1\\}\\) eine NTM. Das Problem hierbei: wir m\u00fcssen \\(y\\), die Eingabe, nun erzeugen und kennen ihre Schranke nicht. Dazu wird auf dem Arbeitsband \\(k+2\\) (\\(k\\) ist die Anzahl der Arbeitsb\u00e4nder der neuen KTM) die Kontrolleingabe \\(y\\) w\u00e4hrend der Simulation der neuen KTM erzeugt. Jeder Schritt der neuen KTM wird durch maximal 4 Schritte simuliert und der Bandbedarf vergr\u00f6\u00dfert sich um 1. Alles konstante Faktoren und unwichtig.<\/p>\n

NTM zur alten KTM<\/strong><\/p>\n

Um den Bogen wieder zur\u00fcck zu schlagen m\u00fcssen alle Verzweigungen durch einen Test auf dem Eingabeband 0 ersetzt werden.<\/p>\n

Antwort zum Lernziel<\/strong>: Die \u00c4quivalenz von Kontrollturingmaschinen und nichtdeterministischen Turingmaschinen begr\u00fcndet sich darin, dass man beide ineinander \u00fcberf\u00fchren kann und die Simulation innerhalb der gleichen Band- und Zeitschranken geschieht (wenn man von den konstanten Faktoren mal absieht).<\/p>\n

Achtung<\/strong>: Bitte verwechselt nicht KTMs und DTMs. Nichtdeterministische Turingmaschinen (NTMs) sind zwar ebenfalls \u00e4quivalent zu deterministischen Turingmaschinen (DTMs), da man NTMs in DTMs \u00fcberf\u00fchren kann. Aber das geschieht nicht<\/strong> innerhalb der gleichen Zeit- und Bandschranken!<\/p>\n

Exkurs: Hamiltonkreisproblem in der KTM<\/h2>\n

Um z.B. das Hamiltonkreisproblem in einer KTM zu entscheiden, m\u00fcssen wir das Problem formalisieren. Dazu wird der Graph als Adjazenzmatrix geschrieben und zeilenweise aufgeschrieben. Als Kontrolleingabe dient dann eine Folge von Knoten und die KTM pr\u00fcft die Eingabe auf die gesuchte Eigenschaft.<\/p>\n

Lernziel 3<\/h2>\n

Definition nichtdeterministischer Komplixit\u00e4tsma\u00dfe und -klassen<\/em><\/p>\n

Da wir KTMs durch NTMs mit den gleichen Schranken simulieren k\u00f6nnen gilt:<\/p>\n

\\(ZEIT(f)\\subseteq NZEIT(f)\\)\n\\(BAND(f)\\subseteq NBAND(f)\\)<\/blockquote>\n

sowie<\/p>\n

\\(NZEIT(f)\\subseteq BAND(f)\\)<\/blockquote>\n

Definieren wir hier auch \\(NZEIT(f)\\):<\/p>\n

\\(NZEIT(f)\\subseteq\\bigcup_{c\\in\\mathbb{N}}ZEIT(c^{f(n)})\\)<\/blockquote>\n

Mit der Menge \\(NZEIT\\) geben wir die Menge der Sprachen an, die von einer nichtdeterministischen Turingmaschine in Zeit \\(O(f)\\) akzeptiert werden k\u00f6nnen (Wikipedia<\/a>).<\/p>\n

Die Reihenfolge darf hier auch nicht fehlen: \\(P\\subseteq NP\\subseteq PSPACE\\subseteq\\bigcup_{c\\in\\mathbb{N}}ZEIT(2^{n^{c}})\\)<\/p>\n

Ebenso der nichtdeterministische Bandbedarf:<\/p>\n

Sei \\(log\\in O(f)\\), so gilt:<\/p>\n

\\(NBAND(f)\\subseteq\\bigcup_{c\\in\\mathbb{N}}ZEIT(c^{f(n)})\\) und \\(LOGSPACE\\subseteq P\\).<\/p>\n

Sowie<\/p>\n

\\(NBAND(f)\\subseteq BAND(f(n)^2)\\) und \\(NPSPACE = PSPACE\\) (Satz von Savitch)<\/p><\/blockquote>\n

Wichtig<\/strong>: noch ein paar Erg\u00e4nzungen zum Satz von Savitch<\/a>: dieser Satz besagt nichts anderes, als dass jedes von einer \\(NTM\\) (nichtdeterministisch, d.h. wir orakeln die L\u00f6sungseingabe) l\u00f6sbares Problem  auch von einer \\(DTM\\) (deterministisch, d.h. wir orakeln nicht) in exponentieller Zeit<\/em> gel\u00f6st werden kann und der Platzbedarf dieser Maschine nur quadratisch<\/em> h\u00f6her liegt. Die Folgerung aus diesem Satz bedeutet, dass die Bandkomplexit\u00e4tsklasse \\(NPSPACE\\) mit der Bandkomplexit\u00e4tsklasse \\(PSPACE\\) \u00fcbereinstimmt.<\/p>\n

Antwort zum Lernziel<\/strong>: Definitionen siehe oben.<\/p>\n

PS<\/strong>: Wie im vorherigen Lernziel angedeutet: verwechselt bitte nicht NTMs\/KTMs\/DTMs. Und merkt euch den Satz von Savitch \ud83d\ude09<\/p>\n

Lernziel 4<\/h2>\n

Zusammenhang zwischen deterministischen und nichtdeterministischen Komplexit\u00e4tsklassen<\/em><\/p>\n

Antwort zum Lernziel<\/strong>: durch die \u00dcberf\u00fchrung der nichtdeterministischen Turingmaschinen in deterministische Kontroll<\/em>turingmaschinen, die die selben Komplexit\u00e4tsklassen in Zeit und Band inne haben besteht hier ein entsprechend enger Zusammenhang.<\/p>\n

Update<\/strong>: Ebenso verh\u00e4lt es sich bei der \u00dcberf\u00fchrung von nichtdeterministischen Turingmaschinen in deterministische Turingmaschinen. Nach Savitch haben diese aber nicht die gleichen Zeit- und Bandschranken.<\/p>\n

Nach dem Satz von Savich<\/a> gilt, dass wenn eine NTM ein Problem polynomiell l\u00f6sen kann, kann eine \u00e4quivalente DTM das Problem in exponentieller Zeit l\u00f6sen. Der Speicherplatzbedarf erh\u00f6ht sich ebenfalls: er wird quadratisch.<\/p>\n

Lernziel 5<\/h2>\n

Definition von \\({}\\leq_{pol}{}\\)<\/em><\/p>\n

Hierzu bem\u00fchen wir noch einmal unsere Definition der Reduzierbarkeit<\/a>: wenn wir Mengen auf andere Mengen reduzieren k\u00f6nne, so gelten die Eigenschaften der kleineren Menge auch f\u00fcr dir gr\u00f6\u00dfere. Der Unterschied zu dem Verfahren in der Komplexit\u00e4tstheorie ist es, dass wir nun Wortfunktionen statt Zahlenfunktionen verwenden und diese \u00dcberf\u00fchrungsfunktionen nur aus einer bestimmten Komplexit\u00e4tsklasse f\u00fcr Funktionen zulassen. Es eignen sich nur Komplexit\u00e4tsklassen, die unter Komposition (wenn sie \\(f,g\\) enthalten, enthalten sie auch \\(f\\circ g\\)) abgeschlossen sind. K\u00e4mpfen wir uns also durch die Definition:<\/p>\n

LOGSPACE und polynomielle Reduzierbarkeit<\/p>\n

\\(L\\) hei\u00dft \\(LOGSPACE\\)-reduzierbar auf \\(M\\) (\\(L\\leq_{log}{}\\)) wenn es eine Funktion \\(f\\) aus der Klasse \\(FLOGSPACE\\) gibt und f\u00fcr alle \\(x\\in L\\) gilt, dass \\(f(x)\\in M\\) ist.<\/p>\n

\\(L\\) hei\u00dft polynomiell-reduzierbar auf \\(M\\) (\\(L\\leq_{pol}{}\\)) wenn es eine Funktion \\(f\\) aus der Klasse \\(FP\\) gibt und f\u00fcr alle \\(x\\in L\\) gilt, dass \\(f(x)\\in M\\) ist.<\/p><\/blockquote>\n

Die \u00dcberf\u00fchrungsfunktion muss f\u00fcr die \\(LOGSPACE\\)-Reduzierbarkeit also aus der logarithmischen Komplexit\u00e4tsklasse stammen, w\u00e4hrend f\u00fcr die polynomielle Reduzierbarkeit gefordert wird, dass die Funktion aus der polynomiellen Komplexit\u00e4tsklasse kommen muss. Damit haben wir den zentralen Satz f\u00fcr unsere Komplexit\u00e4tsklassen:<\/p>\n

LOGSPACE, NLOGSPACE, P, NP, PSPACE sind abgeschlossen gegen \\(\\leq_{log}{}\\), P, NP, PSPACE aber auch gegen \\(\\leq_{pol}{}\\)<\/p>\n

Die meisten von euch werden das „F“ vor *SPACE schon korrekt gedeutet haben. Da ich aber selbst kurz dr\u00fcber nachgedacht habe, es im Skript aber nur in einem Nebensatz gefallen ist, m\u00f6chte ich noch einmal darauf hinweisen. W\u00e4hrend wir in z.B. in LOGSPACE, P, … Sprachen <\/strong>(die in der Zeit entschieden werden k\u00f6nnen) drin liegen haben, haben wir in FLOGSPACE, FP, … aber Funktionen<\/strong>. Diesen Unterschied solltet Ihr im Kopf behalten (Danke Barbara).<\/p>\n

Antwort zum Lernziel<\/strong>: Mit der polynomiellen Reduktion ist es uns m\u00f6glich mit Angabe einer Funktion (die innerhalb der polynomiellen Komplexit\u00e4tsklasse ist) eine Menge auf eine andere zu reduzieren und so Eigenschaften der Menge quasi zu „vererben“. Das spielt eine wichtige Rolle bei dem Beweis der \\(NP\\)-Vollst\u00e4ndigkeit von Mengen.<\/p>\n

Lernziel 6<\/h2>\n

Erkl\u00e4rung der Vollst\u00e4ndigkeit<\/em><\/p>\n

K\u00fcmmern wir uns zun\u00e4chst um die Definition aus dem Skript:<\/p>\n

\\(M\\) ist \\(NP\\)-hart wenn \\(L\\in{NP}\\), \\(L\\leq_{pol}{M}\\)<\/p><\/blockquote>\n

Bedeutet: \\(M\\) ist \\(NP\\)-hart wenn es eine Menge \\(L\\) in \\(NP\\) gibt, die wir auf die Menge \\(M\\) in polynomieller Zeit reduzieren k\u00f6nnen. Haben wir also eine Menge \\(L\\), die nachgewiesen \\(NP\\)-hart ist, und k\u00f6nnen wir mit einer polynomiellen \u00dcberf\u00fchrungsfunktion \\(f\\in{FP}:L\\rightarrow M\\) (zu einem \\(x\\) aus \\(L\\) bekommen wir mit \\(f(x)=y\\) ein \\(y\\) aus \\(M\\)) diese Menge auf \\(M\\) reduzieren, so ist die Menge \\(M\\) eben \\(NP\\)-hart.<\/p>\n

Noch einmal dr\u00fcber nachdenken, was \\(NP\\)-hart bedeutet? Das Problem ist mit einer nichtdeterministischen Turingmaschine (NTM) in polynomieller Zeit l\u00f6sbar.<\/del> Das Problem ist dann \\(NP\\)-hart wenn sich alle nichtdeterministisch polynomiell l\u00f6sbaren Probleme darauf reduzieren lassen (danke Barabara). Wie z.B. unser Hammiltonkreisproblem (das ist zudem auch noch \\(NP\\)-vollst\u00e4ndig, aber dazu gleich mehr). Definition gemerkt und verstanden? Gut, dann weiter.<\/p>\n

\\(M\\) ist \\(NLOGSPACE\\)-hart wenn \\(L\\in{NLOGSPACE}\\), \\(L\\leq_{log}{M}\\)<\/p><\/blockquote>\n

Das Selbe in Gr\u00fcn. Nur wird hier die logarithmische Reduzierbarkeit der Menge gefordert. Jetzt kommt das, warum es diesen Abschnitt \u00fcberhaupt gibt. Die Vollst\u00e4ndigkeit:<\/p>\n

\\(M\\) hei\u00dft \\(NP\\)-vollst\u00e4ndig wenn: \\(M\\) \\(NP\\)-hart und \\(M\\in{NP}\\)<\/p><\/blockquote>\n

Wir sprechen hier also von Vollst\u00e4ndigkeit<\/em> wenn \\(M\\) zu der Klasse \\(NP\\) geh\u00f6rt (eine \\(DTM\\) kann in polynomieller Zeit die Richtigkeit der geratenen L\u00f6sung verifizieren) und alle anderen Mengen aus \\(NP\\) mittels einer \u00dcberf\u00fchrungsfunktion \\(f\\) in polynomieller Zeit (d.h. \\(f\\in{FP}\\)) auf die Menge \\(M\\) \u00fcberf\u00fchrt werden k\u00f6nnen. Ist ein langer Satz, lest ihn ein paar Mal langsam durch bis sich bei euch im Kopf ein Bild zeichnet. Damit sind alle \\(NP\\)-vollst\u00e4ndigen Probleme auch \\(NP\\)-hart. Das gleiche gilt dann f\u00fcr \\(NLOGSPACE\\) und \\(P\\):<\/p>\n

\\(M\\) hei\u00dft \\(NLOGSPACE\\)-vollst\u00e4ndig wenn: \\(M\\) \\(NLOGSPACE\\)-hart und \\(M\\in{NLOGSPACE}\\)<\/p>\n

\\(M\\) hei\u00dft \\(P\\)-vollst\u00e4ndig wenn: \\(M\\) \\(P\\)-hart und \\(M\\in{P}\\)<\/p>\n<\/blockquote>\n

Das war schon etwas entspannter als der vorherige Beitrag zu KE2, oder?<\/p>\n

Antwort zum Lernziel<\/strong>: die Vollst\u00e4ndigkeit einer Menge zu einer Komplexit\u00e4tsklasse bedeutet nicht nur, dass die Menge mit einer Turingmaschine erkannt werden kann, deren Schranke innerhalb der Komplexit\u00e4tsklasse liegt. Sondern auch, dass sich alle anderen, vollst\u00e4ndigen Probleme aus dieser Komplexit\u00e4tsklasse darauf reduzieren lassen. Alle Eigenschaften, die wir f\u00fcr eine Klassen-vollst\u00e4ndige Menge darlegen gelten auch f\u00fcr alle anderen Klassen-vollst\u00e4ndigen Mengen.<\/p>\n

Der Vorteil bei vollst\u00e4ndigen Problemen in einer Klasse ist, dass wenn wir es z.B. schaffen f\u00fcr ein \\(NP\\)-Vollst\u00e4ndiges Problem einen polynomiellen Algorithmus anzugeben, der das Problem entscheidet, so haben wir gleichzeitig f\u00fcr alle \\(NP\\)-vollst\u00e4ndigen Probleme einen L\u00f6sungsweg gefunden, da sich diese polynomiell aufeinander (wenn auch mit Zwischenschritten) reduzieren lassen.<\/p>\n

Da wir noch bisschen Platz im Beitrag haben, w\u00fcrden sich vielleicht einige Details zum Begriff Vollst\u00e4ndigkeit hier gut machen:<\/p>\n

Rekapitulation: wozu ist die Vollst\u00e4ndigkeit gut?<\/strong><\/p>\n

(dieser Abschnitt hat das rechts oben verlinkte Buch von Dirk. W. Hoffmann<\/a> – absolute Kaufempfehlung – und diverse Internet-Artikel als Informationsbasis)<\/p>\n

Die Vollst\u00e4ndigkeit ist ein zentrales und wichtiges Werkzeug der theoretischen Informatik. Sie vereinfacht eine Dinge ungemein. Durch die Reduktion k\u00f6nnen wir alte Probleme auf neue reduzieren, d.h. wir vererben quasi Komplexit\u00e4tsaussagen von einer Menge auf eine andere. Was ist hier also der Unterschied zwischen hart und vollst\u00e4ndig? Ein Problem\/eine Menge \\(M\\) ist z.B. \\(NP\\)-hart wenn sich alle Probleme aus der Klasse \\(NP\\) auf dieses reduzieren lassen. Die Menge \\(M\\) selbst muss nicht in \\(NP\\) liegen. Erst wenn die Menge selbst in \\(NP\\) liegt, spricht man von Vollst\u00e4ndigkeit.<\/p>\n

Wie zeigen wir Vollst\u00e4ndigkeit?<\/p>\n

    \n
  1. Zun\u00e4chst m\u00fcssen wir zeigen, dass ein z.B. Problem in der Klasse \\(NP\\) liegt: Wir geben eine \\(NTM\\) an (eine \\(DTM\\) w\u00fcrde sogar auch reichen), die die Eingabe in polynomieller Zeit auf Richtigkeit pr\u00fcft. haben wir das getan, so fehlt uns nur noch der Nachweis der Reduktion:<\/li>\n
  2. Nun zeigen wir die \\(NP\\)-H\u00e4rte: dass mittels polynomieller Reduktion sich alle Mengen aus \\(NP\\) auf unsere untersuchte Menge \\(M\\) reduzieren lassen. Das machen wir, indem wir irgendeine Menge aus \\(NP\\) nehmen, die selbst bereits als vollst\u00e4ndig eingestuft wurde. Warum k\u00f6nnen wir das tun? Durch die Transivit\u00e4t<\/a> der \u00dcberf\u00fchrungsfunktion.<\/li>\n<\/ol>\n

    Done. Ist kein vollst\u00e4ndiges Problem f\u00fcr eine Klasse bekannt, so wird die generische Reduktion angewandt. Ein Beispiel hierzu gab Stephen A. Cook<\/a> (der lebt noch) in seinem ber\u00fchmten Satz<\/a> (f\u00fcr den er auch den Turing-Award bekam). Er zeigte, dass das SAT<\/strong>-Problem \\(NP\\)-Vollst\u00e4ndig ist. Fortan konnte man f\u00fcr andere Mengen mittels Reduktion von SAT<\/strong> auf diese die \\(NP\\)-Vollst\u00e4ndigkeit einfach nach dem oben beschriebenen Verfahren gezeigt werden. Im n\u00e4chsten Beitrag werden wir versuchen \\(SAT\\) als \\(NP\\)-hart zu beweisen ohne die Abk\u00fcrzung mittels Reduzierbarkeit zu nehmen.<\/p>\n

    Welche Vorteile hat die Vollst\u00e4ndigkeit noch?<\/strong><\/p>\n

    Einer der Vorteile der Vollst\u00e4ndigkeit ist die Beziehung zu allen anderen vollst\u00e4ndigen Problemen in der Komplexit\u00e4tsklasse. Nehmen wir z.B. \\(NP\\): gelingt es uns f\u00fcr ein \\(NP\\)-vollst\u00e4ndiges Problem zu zeigen, dass es in polynomieller Zeit l\u00f6sbar ist (schaffen wir z.B. das Hamiltonkreisproblem in deterministischer, polynomieller Zeit zu l\u00f6sen), so sind auch direkt alle<\/strong> anderen vollst\u00e4ndigen Probleme aus der Klasse \\(NP\\) deterministisch polynomiell l\u00f6sbar. Damit w\u00e4re die Beziehung \\(P=NP\\) positiv bewiesen, was als eines der wichtigsten, mathematischen Probleme unserer Zeit gilt. Aus diesem Grund wurde es auch in die Liste der Millenium-Probleme<\/a> aufgenommen. Neben Ruhm und Ehre gibt es oben drauf noch eine Million USD vom Clay Mathematics Institute<\/a>.<\/p>\n

    Damit sind wir auch mit der Kurseinheit 3 durch.<\/p>\n

    Auch wenn ich mich mittlerweile wie eine Schallplatte anh\u00f6re: wer Erkl\u00e4rungs-Fehler findet, bitte ASAP melden damit ich das sofort korrigieren kann.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Update: durch den Hinweis von Philipp ist mir noch etwas aufgefallen. Der Vergleich von deterministischen Turingmaschinen zu nichtdeterministischen ist nicht ganz deutlich r\u00fcber gekommen. Daher habe ich den Abschnitt noch einmal \u00fcberarbeitet (Lernziel 2, 3 und 4). Update: Antworten zu den Lernzielen. Das ist ein sch\u00f6nes Thema. Wirklich. Auch keinerlei Sarkasmus hier drin versteckt. Ich … <\/p>\n

    \u201eTIB: Nichtsdeterministische Komplexit\u00e4t (Lernziele KE3, Update 3)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-1471","post","type-post","status-publish","format-standard","hentry","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1471","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1471"}],"version-history":[{"count":44,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1471\/revisions"}],"predecessor-version":[{"id":3534,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1471\/revisions\/3534"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1471"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1471"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1471"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

Nach dem Satz von Savich<\/a> gilt, dass wenn eine NTM ein Problem polynomiell l\u00f6sen kann, kann eine \u00e4quivalente DTM das Problem in exponentieller Zeit l\u00f6sen. Der Speicherplatzbedarf erh\u00f6ht sich ebenfalls: er wird quadratisch.<\/p>\n