André Vratislavsky

Übungsgruppe vom 11./18.01.2000

Effiziente Berechenbarkeit

Nachdem wir uns mit der Berechenbarkeit von Problemen beschäftigt haben, stellen wir uns nun die Frage, Wie effizient eine Funktion berechenbar ist. Dabei interessieren uns obere bzw. untere Schranken für die Laufzeit. Im Folgenden betrachten wir die Komplexitätsklasse P der in polynomieller Zeit berechenbaren Funktionen.
Dabei kommt es nicht auf das Rechnermodell an, da sich TM's mit unterschiedlicher Anzahl von Bändern und RAM's in polynomieller Zeit simulieren lassen.
Ein erstes Problem ist TSP (s. Vorlesung).
An Beispielen sieht man, daß es oft schwierig ist, eine Lösung zu finden.
Reines Probieren aller denkbaren Kombinationen liegt oft in einer exponentiellen Zeit, da es z.B. bei Graphproblemen oft n! viele Kombinationen gibt. Dies schließt aber nicht aus, mit einem anderen Algorithmus das Problem in kürzerer Zeit lösen zu können. Das Verifizieren einer irgendwie geratenen richtigen Lösung ist aber oft in polynomieller Zeit möglich.
Ein Beispiel ist, einen Weg in einem Graphen (mit n Knoten), z.B. einem Labyrinth zu finden. Das Ablaufen aller möglichen Wege von Knoten a nach b würde das Durchprobieren von n! vielen Pfaden erfordern. Breitensuche merkt sich alle n besuchten Knoten und besucht sie nur einmal. (Das geht natürlich nur, wenn man eine globale Sicht auf das Labyrinth hat, d.h. die Knoten verzeigern kann.)
Ein Ansatz ist die nichtdeterministische Turingmaschine (NTM). Sie "rät" die gesuchte Lösung nichtdeterministisch und verifiziert sie deterministisch. Alle Sprachen, die von einer NTM in polynomieller Zeit akzeptiert werden, gehören zur Klasse NP. Auf diese Weise kann aber nicht bewiesen werden, daß eine Sprache zu P gehört, da NTM's vermutlich nicht in polynomieller Zeit von deterministischen TM's simuliert werden können. (Es müssen exponentiell viele Rechenwege simuliert werden.)
Auf Grund der Problematik nimmt man an, daß P ungleich NP ist.

Zusammenfassung:

P ist die Klasse der effizient entscheidbaren Probleme.
NP ist die Klasse der effizient verifizierbaren Probleme.
Vermutlich ist P eine echte Teilmenge von NP.

Polynomielle Reduktion

Eine Möglichkeit, Probleme bezüglich ihrer "Schwierigkeit" zu vergleichen, ist die polynomielle Reduktion.

Definition:

L1 ist in polynomieller Zeit auf L2 reduzierbar (L1'<=p' L2)
gdw. es eine überall def. poynomiell zeitbeschränkte berechenbare Funktion f gibt, so daß für alle Wörter w gilt: w aus L1 <=> f(w) aus L2
Sprechweise: "L1 ist bis auf einen polynomiellen Zeitfaktor nicht schwieriger als L2 "

Aus dieser Definition folgt:

(L2 aus P) impliziert (L1 aus P)

Eine Sprache L heißt NP-vollständig, wenn sie aus NP ist und alle anderen Sprachen aus NP "(bis auf polynomiellen Faktor) nicht schwieriger sind". L gehört dann zu einem "schwersten Problem".
Würde man für ein NP-vollständiges Problem X nachweisen, daß es nicht in P liegt, so wüßte man das dann auch automatisch für alle anderen NP-vollständigen Probleme, da X ja "nicht schwieriger als" diese ist. Die anderen NP-vollständigen Probleme sind also "erst recht" nicht in P.
Es ist also von Interesse, NP-Vollständigkeit nachzuweisen. Dies kann mit obigem Reduktionsschema geschehen:

[ (L1 NP-vollständig) und (L2 aus NP) und (L1'<=p' L2) ] impliziert [ L2 ist NP-vollständig ]

Man muß nun noch für ein erstes Problem die NP-Vollständigkeit mit einer anderen Methode nachweisen, da für obigen Satz ein NP-vollständiges Problem benötigt wird. Dies geschah in der Vorlesung für das SAT-Problem. (SAT ist die Menge der erfüllbaren Formeln der Aussagenlogik.)