Komplexitätstheorie

Komplexitätstheorie beschäftigt sich mit der Theorie des Berechnens. Genauer mit der Komplexität von Problemen, die mit Berechnungen gelöst werden. Komplexität bezieht sich dabei auf das Maß der Verwendeten Ressourcen. Hierbei gibt es Zeit und Platz, wobei beide eng miteinander verwandt sind (?).

Die Krux und Schwierigkeit von Komplexitätstheorie: Fokus auf der $\textbf{intrinsischen}$ Komplexität von Problemen.

Ein Problem kann sein: Ist Zahl X eine Primzahl? Sind diese beiden Graphen isomorph? Was ist die Lösung für dieses Sudoku? etc.

Ein Algorithmus ist dann eine ganz konkrete Abfolge von Befehlen um ein Problem zu lösen, so dass man mit völlig stupider Einhaltung der Regeln auf jeden Fall zum Ziel kommt. Das kann ein Programm in Python oder C++ sein, oder theoretischer eine Turing-Maschine.

Jetzt ist die Komplexität eines bestimmten Algorithmus für ein Problem hier nicht so interessant. Es geht um die intrinsische Komplexität, also was ist die Komplexität, unabhängig davon welchen Algorithmus ich wähle. (Ein Problem kann unendlich viele unterschiedliche Algorithmen haben) Welche Komplexität wohnt dem Problem inne und ist nicht von der genauen Gestalt eines Algorithmus abhängig? Das macht die Schwierigkeit aus.

Anmerkung: Die Begriffe Problem, Algorithmus und Ergebnis sind sehr eng miteinander verbunden. Ein Problem: Finde alle Primzahlen, Ein Algorithmus: (Abfolge von Befehlen um Primzahlen zu berechnen), das Ergebnis: eine Liste von Primzahlen.

Alle drei verschiedene Blickwinkel auf die selbe Sache?

Wenn ich den Begriff des Problems genauer beschreibe, (also was ist genau eine Primzahl, eine Zahl die nur durch 1 und sich selbst teilbar ist, was bedeutet teilbar etc..) dann lande ich letzlich bei der Beschreibung meines Problems fast schon bei einem Algorithmus wie die Lösung zu berechnen ist. (Je nach dem, wie ich den Begriff Primzahl beschreibe, es wäre auch eine andere Beschreibung denkbar und dann ein anderer Algorithmus). Es gibt also unterschiedliche Perspektiven auf ein Problem. Was ist das Problem ohne Perspektive, also intrinsisch? Das schein Stand heute nicht wirklich klar zu sein, da hier viele Ansätze scheitern und man keine Aussagen treffen kann.

P

Die Komplexitätsklasse P ist die Menge aller Probleme die von einer deterministischen Turing-Maschine in polynomieller Zeit gelöst werden können. Die Lösung des Problems zu verfizieren ist dann quasi das selbe als den Algorithmus auszuführen. (Z.b. Multiplikation)

NP

NP ist die Menge aller Probleme die von einer nichtdeterministischen Turing-Maschine (TM mit “Wahlmöglichkeiten”, dabei wird jede Wahl getroffen) in polynomieller Zeit gelöst werden können. Anders: Eine deterministische TM die zusätzlich zur Eingabe X auch einen Zeugen (quasi die Lösung) bekommt, und dann in polynomieller Zeit nur verfizieren muss, das der Zeuge das Problem löst für X. Z.b. X ist als Eingabe ein Sudoku Feld und der Zeuge ist die Belegung der restlichen Felder. Jetzt kann in polynomieller Zeit überprüft werden ob die Lösung richtig ist.

NP sind dann u.a. Rätsel, es ist Schwierig, bzw. unklar wie eine Lösung gefunden werden kann (im Zweifelsfall nur durch ausprobieren aller Möglichkeiten), aber wenn eine Lösung gefunden wurde, ist es einfach Einzusehen das es eine Lösung ist.

NP-Vollständig

Ein Problem heißt NP-Vollständig wenn es in NP liegt und NP-Hart ist.

NP-Hart:

Ein Problem heißt NP-Hart wenn jedes Problem (Element) aus NP in polynomieller Zeit auf dieses (NP-Harte) Problem reduziert werden kann. Das NP-Harte Problem kann quasi jedes andere Problem effizient simulieren.

Bspw. ist das Halteproblem trivialerweise NP-Hart (und Hart für alles), da jedes Problem das Berechenbar ist, auf das Halteproblem reduziert werden kann. Aber das Halteproblem liegt nicht in NP (es ist ja unberechenbar..).

SAT ist NP-Vollständig. (Fast jedes Problem ist NP-Vollständig, es ist kein natürliches Problem bekannt, welches nicht NP-Vollständig ist)

Die Frage N = NP?

Eine der sieben Millenium Fragen der Wissenschaft. Gibt es effiziente Algorithmen für wichtige Probleme wie SAT, TSP, etc? Ist alles was effizient verifizierbar ist auch effizient Berechenbar? Jedes NP Problem beinhaltet eine Suche über einen Raum vieler Möglichkeiten, ist diese Suche vermeidbar?

Auf Musik bezogen: Ist eine Beethoven Sonate zu komponieren das Gleiche wie sie zu verstehen beim anhören? (Anmerkung: Ich würde sagen eine gegeben Komposition zu verifizieren, das es eine “gute” Komposition ist, kann sehr schwierig sein, liegt außerhalb der N=NP Frage)

Schwierigkeit der N = NP Frage:

Es konnte gezeigt werden das bestimmte Beweistechniken nicht verwendet werden können um dieses Problem zu lösen. Genauer relativierende Beweistechniken wie Diagonalisierung. (Dieser Beweis verwendet Diagonalisierung..)

Diagonalisierung

Elementare Beweistechnik.(siehe Cantors Beweis zur Überabzählbarkeit) Hier wird jeder TM als Nummer dargestellt, um wieder als Eingabe für eine andere TM zu dienen (Universelle TM) => Gödelisierung. Jetzt sind alle TMs systematisch aufzählbar in einer Liste, dann kann über die Diagonale eine neue TM/Sprache konstruiert werden die dann (nach annahme) nicht in der Liste auftauchen kann. Diese Beweistechnik reicht bei N=NP alleine nicht aus.

PSCPACE

Die Menge PSPACE ist die Menge aller Probleme die in polynomiellen Platz berechnet werden können. (Also jetzt Platz statt Zeit)

In PSPACE liegen Spiele. Also Probleme bei denen selbst gegeben eine Lösung (gegeben eines optimalen Spielzuges im Schach) es immer noch sehr schwierig ist dann einzusehen das diese Lösung tatsächlich korrekt ist.

(Dieser Artikel ist entstanden durch die Vorlesung Komplexitätstheorie von Dennis Hofheinz am KIT)