Lektion 11: Berechenbarkeit & P vs. NP

Diese Lektion bietet eine kurze Einführung in die größten Errungenschaften der theoretischen Informatik: das Abstecken der Grenzen der prinzipiellen Berechenbarkeit und der Polynomial-Zeit-Berechenbarkeit. Letzteres bringt uns auch zu einer der grundlegendsten und bedeutendsten offenen Fragen unserer Zeit: P = NP?

Auf dem Weg dort hin werdet ihr lernen, Computer und Berechnungen aus einem völlig neuen Blickwinkel zu betrachten: Was ist die minimale Fähigkeit, die eine Maschine haben muss, um die prinzipiellen Möglichkeiten moderner Computer zu erreichen? Es zeigt sich, dass ein äußerst primitives mathematische Modell, die Turing-Maschine, schon die gleiche Mächtigkeit wie jeder physikalisch denkbare Computer zu haben scheint.

Anhand dieses einfachen Modells werdet ihr lernen, dass es Probleme gibt, auf die Computer mathematisch beweisbar keine Antwort liefern können.

Unter den prinzipiell lösbaren Problemen gibt es eine Vielzahl, für die nur unbrauchbar langsame Algorithmen bekannt sind, genauer: es ist kein Algorithmus bekannt, dessen worst-case Laufzeit eine polynomielle order of growth hat, der also für ein festes k in O(n^k) arbeitet. Ob es solche Algorithmen gibt (und sie nur noch keiner, trotz intensiver Bemühungen, gefunden hat) oder nicht, ist ein offenes Problem, das als Frage »P = NP?« abgekürzt wird. Es gibt aber die Theorie der NP-Vollständigkeit, die genaue Aussagen zulässt, wie hoffnungslos die Suche nach solchen schnellen Algorithmen für gewisse Probleme ist.

Auch wenn die Aussagen in dieser Lektion sehr abstrakt bleiben, haben sie direkte Konsequenzen für praktische Anwendungen; insbesondere lohnt es sich zu lernen zu erkennen, wann einem jemand eine (beweisbar oder höchstwahrscheinlich) unmögliche Aufgabe anbefiehlt.

Lernziele

• Ein Beispiel für ein nicht berechenbares Problem kennen,
• in einfachen Fällen nachweisen können, dass ein Problem nicht berechenbar ist,
• die Frage hinter »P=NP?« anschaulich beschreiben können,
• Evidenz liefern für die Vermutung P≠NP,
• in einfachen Fällen nachweisen können, dass ein Problem NP-vollständig ist,
• Lösungsansätze anwenden können, um in der Praxis mit NP-vollständigen Problemen umzugehen.

Fragensammlung für die Q&A Session

Tragt hier Fragen ein, die während der Vorbereitung aufkamen, und die ihr gerne klären möchtet. Bewertet außerdem die existierenden Fragen.

Hausordnung

• Es ist explizit erlaubt/erwünscht, Fragen aus den Aufgaben zur Vorbereitung unter den Videos zu übernehmen, wenn ihr diese der Q&A Session besprechen wollt.
• Auch wenn ihr gerade keine eigene Frage stellen möchtet, sind die Fragen der anderen oft hilfreiche Denkanstöße auch für euch. Deshalb, und um Fragen für die Q&A Sessions zu priorisieren, könnt ihr Fragen bewerten.
  Tragt dazu bei einer Frage entweder ein (zusätzliches) »+« ein, wenn ihr diese Frage interessant findet, oder ein (zusätzliches) »-«, wenn ihr sie nicht hilfreich findet (z.B. weil die Antwort direkt im Video gegeben wird). Listet zur besseren Übersicht zuerst alle »+«, dann alle »-«, jeweils in 5er Gruppen.
• Bevor ihr eine neue Frage eintragt, schaut ob eine existierende Frage eurer sehr nahe kommt; wenn ja, schreibt eure Frage als alternative Formulierung zu dieser Frage dazu.
• Wenn ihr der Meinung seid, ihr könnt eine Frage in wenigen Worten beantworten, so ergänzt eure Antwort unterhalb der Frage. Auch diese Antworten könnt ihr bewerten, wenn ihr sie hilfreich findet, oder Erwiderungen ergänzen, wenn ihr sie für falsch haltet.
• Seid konstruktiv.

Material

Teil 1, Teil 2, Teil 3, optionale Themen.

Die Videos entstammen der Princeton Vorlesung Introduction to Computer Science von Robert Sedgewick und Kevin Wayne.

Die Videos wurden von Kevin Wayne exklusiv für A&DS zur Verfügung gestellt und sind deshalb nur mit Passwort abrufbar. Da es dieses Feature bei Youtube nicht gibt, sind sie bei vimeo gehostet; dort gibt es leider die beschleunigte Wiedergabe nicht. Im HTML5-Video Player kann man sie aber über Browser-Plugins nachrüsten: Firefox, Chrome. Leider funktionieren diese widerum nur in der vollen Ansicht, nicht für die eingebetten Player auf dieser Seite.

Das Passwort für die Videos erhaltet ihr im Kurs.

Teil 1 – Motivation und Denkweisen der theoretischen Informatik

Diese Lektion ist in ihren Aussagen weit abstrakter als die vorhergehenden, daher gibt Teil 1 einen Überblick über die Ziele der theoretischen Informatik.

1.1 – Introduction to Theoretical Computer Science

In diesem Video gibt Sedgewick einen Überblick über die Philosophie und Ziele der theoretischen Informatik (theoretical computer science, TCS). Ein herausragendes Merkmal der Informatik ist es, dass viele Ergebnisse der theoretischen Forschung direkte Verwendung in der Praxis finden; Sedgewick gibt Beispiele, die diese Behauptung untermauern.

Im letzten Teil des Videos gibt Sedgewick einen Ausblick auf einen Teil von TCS (REs and DFAs), den wir in A&DS nicht behandeln, der aber einen guten Einstieg in die Denkweise von TCS ermöglicht.

Wenn du schon immer wissen wolltest, was reguläre Ausdrücke sind, und wie man damit arbeitet, findest du die ausgelassenen Videos im optionalen Teil.

Aufgaben zur Vorbereitung:

1. Was sind laut Sedgewick die fundamentalen Fragen in TCS?
2. Was versteht man unter abstract maschines?
3. Welche Anwendungen von TCS-Ergebnissen nennt Sedgewick?

1.2 – Context on Formal Systems

Dieses Video liefert eine kurze Historie der Theorie von Beweisbarkeit und Logik. Ein formales System (formal system) ist in diesem Zusammenhang eine Menge von logischen Regeln, die es erlaubt durch stures Verwenden von (»typographischen«) Regeln Aussagen zu beweisen. Die Frage der Berechenbarkeit, um die es uns in dieser Lektion geht, ist aus diesem Kontext hervorgegangen.

Aufgaben zur Vorbereitung:

1. Welche beiden »Unvollständigkeit« der Mathematik nennt Sedgewick?

Teil 2 – Grenzen der Berechenbarkeit

In Teil 2 werden wir die allgemeine Frage thematisieren, was ein Computer eigentlich ist und was er nicht ist, um dann den Beweis zu führen, dass es für unsere Computer prinzipielle Grenzen gibt: Wir werden Beispiele von Problemen kennen lernen, die sich definitiv nicht im Allgemeinen automatisch lösen lassen.

2.1 – Turing Machines

Dieses Video beschreibt die Turing-Maschinen (Turing machine, TM) als ein denkbar einfachstes Modell für Computer und Berechnungen. Neben der Definition gibt Sedgewick mehrere Beispiele und erklärt, wie man eine TM in Java simulieren kann.
Sedgewick erwähnt mehrfach DFAs (deterministic finite automata); diese Verweise dürft ihr ignorieren.

Es mag den Verständnis dienlich sein, sich dennoch das Video zu endlichen Automaten (DFAs) im optionalen Teil anzusehen, da DFAs eine vereinfachte Vorstufe zu Turing Maschinen darstellen.

Aufgaben zur Vorbereitung:

1. Aus welchen »Bestandteilen« ist eine TM aufgebaut?
2. Wie arbeitet eine TM? Beschreibe einen »Schritt« der Maschine.

2.2 – Universality

Die vielleicht größte Errungenschaft heutiger Computer überhaupt ist, dass man mit einem einzigen Gerät, derselben universellen Hardware, alle möglichen Aufgaben erledigen kann; insbesondere auch solche, die zum Zeitpunkt der Konstruktion dieses Computers noch gar nicht erfunden waren! Voraussetzung dafür ist, dass man einen Computer »zur Laufzeit« programmieren kann; eine Eigenschaft, die man sich wissentlich vor Augen führen muss, weil sie uns so ganz und gar selbstverständlich geworden ist.

Dieses Video skizziert, wie man ein solches universelles Verhalten in den primitiven Turing-Maschinen erreichen kann. Die Bedeutung dieser Möglichkeit, der Existenz universeller TM, ist weitreichend, denn sie führt zum zentralen Begriff der Simulation eines Berechnungsmodells mithilfe eines anderen Berechnungsmodells: Es genügt jetzt, die eine universelle TM in einem anderen Modell zu simulieren, um zu beweisen, dass alle denkbaren TM simuliert werden können.

Auf diese Weise kam man zu dem verblüffenden Ergebnis, dass alle bisher erdachten Berechnungsmodelle sich gegenseitig simulieren können, und somit alle gleich ausdrucksstark sind.

Der Abschnitt über Conway's Game of Life ist nicht Klausur-relevant. (Die Animationen fand ich aber zu hübsch um sie zu entfernen.)

Aufgaben zur Vorbereitung:

1. Beschreibe (grob) die vorgestellte Text-Kodierung einer TM.
2. Welche (groben) Schritte muss eine universelle TM leisten, um eine ihr auf dem Eingabeband gegebene TM zu simulieren?
3. Was besagt die These von Church und Turing?

2.3 – Computability

In diesem Video beschreibt Sedgewick zwei bewiesenermaßen nicht-berechenbare Probleme: Das Post'sche Korrespondenzproblem (Post's correspondence problem, PCP) und das Halteproblem (halting problem). Für letzteres gibt Sedgewick den berühmten anschaulichen Beweis der Nicht-Berechenbarkeit, der auf dem Paradoxon des Epimenides (dem Lügner-Paradox) beruht.

Beide Probleme haben als Ausgabe lediglich ein Ja oder Nein; das ist typische für TCS-Betrachtungen. Man nennt solche Probleme Entscheidungsprobleme und sagt sie sind unentscheidbar (undecidable), wenn sie nicht berechenbar sind.

Aufgaben zur Vorbereitung:

1. Beschreibe anschaulich die Eingabe und Fragestellung des PCP.
2. Beschreibe anschaulich die Eingabe und Fragestellung des Halteproblems.
3. Was ist das Lügner-Paradoxon?
4. Sedgewick verwendet im Beweis der Nicht-Berechenbarkeit eine Method boolean halt(String f, String x). Welche Bedeutung haben dabei f und x? Was soll der Rückgabewert von halt sein? Sei präzise!
5. Wie argumentiert Sedgewick, dass es diese Method halt nicht geben kann?

2.4 – Implications

In diesem Video diskutiert Sedgewick, welche Schlussfolgerungen aus der Existenz nicht berechenbarer Probleme zu ziehen sind, und listet ein Menge weitere solcher Probleme.

Aufgaben zur Vorbereitung:

1. Welche weiteren unentscheidbaren Probleme nennt Sedgewick? Wähle zwei Probleme aus und beschriebe im Detail, was die Eingabe und Fragestellung ist.

Teil 3 – NP-Vollständigkeit und Komplexitätstheorie

In diesem Teil beziehen wir neben der prinzipiellen Lösbarkeit wieder die Laufzeit mit ein und kommen schließlich zur großen Frage P=NP?

3.1 – Intractability

In diesem Video gibt Sedgewick die grundlegenden Definitionen für diesen Teil: Polynomialzeit (poly-time), effiziente Algorithmen (efficient algorithms), effizient lösbare Probleme (tractable problems). Zuerst aber gibt er einen Abriss der Historie und motiviert anhand eines Beispiels (dem Traveling Salesperson Problem, TSP), dass prinzipielle Berechenbarkeit alleine in diesem Universum wenig wert ist.

Aufgaben zur Vorbereitung:

1. Was ist die Eingabe und Ausgabe beim TSP?
2. Was ist ein »UBERcomputer«?
3. Welche Eingabegröße für TSP könnte ein UBERcomputer per brute-force lösen?
4. Wann hat ein Algorithmus »polynomielle Laufzeit«?
5. Wann nennen wir (in dieser Lektion) einen Algorithmus effizient? Sei präzise.
6. Wann ist ein Problem intractable (nicht effizient lösbar)?
7. Welche vier allgemeinen mathematischen Probleme definiert Sedgewick? Welche davon sind tractable (nach aktuellem Wissensstand)?

3.2 – P and NP

In diesem Video definiert Sedgewick die Komplexitätsklassen P und NP als Klassen von Suchproblemen inklusive einer Reihe von Beispielen. Anschließend stellt er P=NP Frage und diskutiert ihre direkten und weiterführenden Konsequenzen.

Aufgaben zur Vorbereitung:

1. Was ist ein Suchproblem (search problem)? Was ist ein Verifizierer? Was ist NP?
2. Welche Beispiele für NP-Probleme nennt Sedgewick? Beschreibe für eines davon was Eingabe, Fragestellung und Suchraum sind, und wie ein Verifizierer für das Problem funktioniert.
3. Was ist P? Was ist der Unterschied zu NP?
4. Welche übertragenen Konsequenzen von P=NP bzw. P≠NP nennt Sedgewick?

3.3 – Poly-time Reductions

In diesem Video beschreibt Sedgewick den Begriff der Polynomialzeit-Reduktion (poly-time reduction) von Problemen, und wie man damit die Nicht-Effizient-Lösbarkeit eines Problems auf ein neues übertragen kann.

Aufgaben zur Vorbereitung:

1. Welche Arbeitshypothese nimmt Sedgewick zu Beginn an?
2. Was bedeutet es, ein Problem X auf ein Problem Y polyzeit-zu-reduzieren (X→Y)? Sei präzise.
3. Was bedeutet die Aussage, Polyzeit-Reduktionen sind transitiv?
4. Welche zwei Ziele kann man laut Sedgewick mittels Reduktionen erreichen?
5. Wie reduziert Sedgewick SAT auf ILP? (Und was waren SAT und ILP gleich wieder?)
6. Welche weiteren Probleme nennt Sedgewick auf die SAT sich reduzieren lässt?

3.4 – NP-Completeness

Mit den Polyzeit-Reduktionen haben wir alle Zutaten zusammen um den wichtigen Begriff der NP-Vollständigkeit zu definieren: auf ein NP-vollständiges Problem lassen sich alle Probleme aus NP polyzeit-reduzieren. Das bedeutet sofort, dass mit einem Polyzeit-Algorithmus für ein einziges NP-vollständiges Problem implizit auch ein Polyzeit-Algorithmus für jedes NP-Problem vorliegt. Dieser Umstand ist der Grund, warum man davon ausgehen kann, dass ein NP-vollständiges Problem wohl keine effiziente Lösung haben dürfte: Schließlich versuchen sich schon seit Jahrzehnten viele Forscher weltweit daran, für all die NP-Probleme einen effizienten Algorithmus zu finden, ohne dass es bisher auch nur für eines gelungen wäre.

Um diese Argumentation anzuwenden, muss man aber erst einmal die NP-Vollständigkeit eines Problems nachweisen, was am einfachsten gelingt, indem man ein neues Problem auf ein schon bekanntermaßen NP-vollständiges polyzeit-reduziert. Dazu braucht man wiederum ein ersten NP-vollständiges Problem. Sedgewick skizziert deshalb den Nachweis der NP-Vollständigkeit der Mutter aller NP-vollständigen Probleme: SAT.

Aufgaben zur Vorbereitung:

1. Wann ist ein Problem NP-vollständig? Sei präzise.
2. Skizziere ganz grob wie Sedgewick begründet, dass SAT NP-vollständig ist.
3. Was bedeutet das für die Liste von Problemen aus Video 3.3, also die Probleme auf die sich SAT polyzeit-reduzieren lässt?

3.5 – Living with Intractability

Nachdem wir gesehen haben, dass man für viele Probleme keinen effizienten Algorithmus erwarten darf, stellt Sedgewick in diesem Video die Frage, wie damit (in der Praxis) umzugehen ist. Neben einigen allgemeinen Ideen, wie man trotz NP-Vollständigkeit ein Problem anpacken kann, zeigt Sedgewick auch Beispiele aus der Kryptographie, wo man sich die Komplexität einiger Probleme zu Nutzen macht.

Aufgaben zur Vorbereitung:

1. Welche Gründe kann es haben, dass sich einige NP-vollständige Probleme (z.B. SAT, TSP, ILP) in der Praxis doch schnell (genug) lösen lassen, (und das auch noch ohne UBERcomputer)?
2. Die Komplexität welches Problems macht sich die Kryptographie zu Nutze?