NP-vollständige Probleme

Effizient lösbare Probleme

Ein Algorithmus zur Lösung eines Problems der Größe n wird als effizient bezeichnet, wenn er eine Zeitkomplexität von O(n^k) hat, wobei k eine Konstante ist. Beispielsweise ist ein Algorithmus mit einer Zeitkomplexität von Θ(n²) effizient, dagegen ein Algorithmus mit einer Zeitkomplexität von Θ(2ⁿ) nicht.

Die Unterscheidung zwischen Problemen, die effiziente Lösungsalgorithmen haben und Problemen, die keine effizienten Lösungsalgorithmen haben, ist äußerst wichtig – die Frage ist nur, woran man erkennt, zu welcher der beiden Klassen ein Problem gehört. Wir hatten bei den Graphenalgorithmen gesehen, dass von zwei ähnlich aussehenden Graphenproblemen, nämlich Berechnung der kürzesten Wege und der kürzesten Rundreise, nur das erste einen effizienten Lösungsalgorithmus hat. Aber kann es nicht sein, dass auch das zweite einen effizienten Lösungsalgorithmus hat, dieser nur noch nicht gefunden ist? Die Antwort ist: im Prinzip ja, andererseits auch wieder nein.

Zwar ist nicht bewiesen, dass die Berechnung der kürzesten Rundreise (das Travelling-Salesman-Problem – TSP) nicht effizient lösbar ist, aber das Gegenteil auch nicht. Ein Indiz dafür, dass TSP effizient lösbar ist, kann darin gesehen werden, dass TSP immerhin einen effizienten nichtdeterministischen Lösungsalgorithmus hat. Ein Indiz dagegen ist, dass TSP zu den schwersten Problemen gehört, die effiziente nichtdeterministische Lösungsalgorithmen haben.

Auf den folgenden Seiten sollen die Grundzüge der Theorie hierzu entwickelt werden mit dem Ziel, zumindest ein Gefühl dafür zu vermitteln, wann ein Problem möglicherweise prinzipiell nicht effizient lösbar ist. Wir bewegen uns hier im Grenzgebiet zur Theoretischen Informatik; daher begnügen wir uns hier teilweise mit einer informellen Darstellung des Themas.

Weiter mit: [Reduktion von Problemen] oder