Albert-Ludwigs-Universität Freiburg
	Institut für mathematische Logik und Grundlagen der Mathematik

Vorlesung Komplexitätstheorie im WS 1998/99

Komplexitätstheorie beschäftigt sich mit der Frage, warum sich viele algorithmische Probleme nur sehr ineffizient lösen lassen.

Mathematisch läßt sich diese Frage im Rahmen der Berechenbarkeitstheorie formulieren. Dort lassen sich auf exakte Weise verschiedene Komplexitätsmaße wie Rechenzeit- oder Speicherplatzbedarf eines Problems definieren. Man kann nun Probleme gemäß dieser Komplexitätsmaße klassifizieren, Probleme einer Komplexitätsklasse sollten dann ungefähr gleich schwer zu lösen sein.

Das Hauptproblem besteht nun darin, das Verhältnis der Komplexitätsklassen untereinander zu bestimmen. Die diesem Problem zugrunde liegenden mathematischen Fragen werden sehr schnell äußerst schwierig, neben einigen schönen Sätzen zeichnet sich die Komplexitätstheorie auch durch zahlreiche noch offene Probleme aus. Suggestiv formuliert lautet das wichtigste unter diesen: Ist es schwieriger, einen Beweis zu finden, als ihn zu verifizieren?

Vorausgesetzt werden in der Vorlesung einige Grundbegriffe der Berechenbarkeitstheorie, wie sie zum Beispiel in den Vorlesungen "Einführung in die mathematische Logik" oder auch "Algorithmen und Berechenbarkeit" zur Verfügung gestellt werden.