parametrisierte Komplexität

Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP-vollständigen Problemen effizient zu lösen sind. Dabei wird untersucht, von welchen Faktoren (Parametern) die Laufzeit der Algorithmen im Wesentlichen abhängt. Zum Beispiel sind viele Graphen-Probleme schnell lösbar für Graphen mit kleiner Baumweite. Formal ist ein Problem parametrisierbar (auch: fixed parameter tractable oder FPT), wenn ein Algorithmus existiert, der es mit einer Laufzeit von löst, wobei f eine berechenbare Funktion, k der Parameter, p ein beliebiges Polynom und n die Eingabelänge (z. B. bei Graphenproblemen die Anzahl der Knoten und Kanten) ist. Man beachte, dass ein Problem mit unterschiedlichen Parametern sowohl FPT, als auch nicht-FPT sein kann. Zum Beispiel ist das Cliquenproblem nicht-FPT, wenn der Parameter die Größe einer maximalen Clique ist, aber FPT, wenn der Parameter die Baumweite oder der Maximalgrad ist. Man sagt auch, dass ein Problem parametrisierbar in dem entsprechenden Parameter ist, z. B. "Das Cliquen-Problem ist parametrisierbar in der Baumweite".Anschaulich ist ein Parameter, in dem ein NP-vollständiges Problem parametrisierbar ist, eine Eigenschaft, die das exponentielle Wachstum der Laufzeiten verursacht, da diese Probleme schnell lösbar sind, bis auf Instanzen, bei denen dieser Parameter groß ist. In der Praxis ist f oft eine unangenehme Funktion wie , man geht im Allgemeinen aber davon aus, dass k sehr klein ist (weil dies bei Instanzen, die in der Praxis vorkommen, häufig der Fall ist) und n groß werden kann. Parametrisierte Algorithmen sind in der Praxis (wo k klein ist) auch für n=50–100 praktikabel, wogegen z. B. gewöhnliche Brute-Force Algorithmen mit Laufzeiten wie schon ab etwa n=20 nicht mehr praktikabel sind. Das Gebiet wurde von Rod Downey und Michael Fellows in den 1990er Jahren begründet.