Worum geht es in dieser Aktivität?

Eines der interessanten Dinge an der Eiswagen-Problematik ist, dass niemand weiß, ob es einen Algorithmus gibt um eine minimale Anzahl von Orten zu finden, der wesentlich schneller ist als die Brute-Force-Methode!

Die Zeit, die die Brute-Force-Methode braucht, wächst exponentiell mit der Anzahl der Kreuzungen - man spricht von einem exponentiellen Algorithmus oder Exponentialzeitalgorithmus. Ein Polynomialzeitalgorithmus (oder auch: polynomieller Algorithmus) ist einer, dessen Laufzeit mit dem Quadrat oder der dritten Potenz oder irgendeiner anderen Potenz der Anzahl von Kreuzungen wächst. Ein Polynomialzeitalgorithmus wird für ausreichend große Straßenkarten - sogar (sagen wir) für einen Algorithmus mit Laufzeit der siebzehnten Potenz - immer schneller sein, da eine exponentiell wachsende Funktion jede polynomiell wachsende Funktion überwiegt, sobald ihr Argumen groß genug wird. (Probiere es an folgendem Beispiel aus: wenn n größer ist als 117, dann ist n17 kleiner als 2n).

Gibt es einen Polynomialzeitalgorithmus, um die minimale Anzahl von Standorten zu finden? - Niemand weiß es, obwohl man sehr bemüht ist, einen zu finden. Das gleiche gilt für die scheinbar einfachere Aufgabe zu überprüfen, ob eine bestimmte Menge von Standorten minimal ist: Der Brute-Force-Algorithmus, der alle Möglichkeiten für kleinere Mengen von Standorten ausprobiert, ist exponentiell abhängig von der Anzahl der Kreuzungen, und polynomielle Algorithmen wurden bisher nicht entdeckt oder es konnte auch nicht bewiesen werden, dass diese gar nicht existieren.

Erinnert dich das an die Färbung der Karte (Aktivität 13)?

Das sollte es. Die Eiswagen-Frage, die offiziell als Bestimmung minimaler Absorptionsmengen bezeichnet wird, ist eines von vielen Tausend Problemen, für die nicht bekannt ist, ob Polynomialzeitalgorithmen in Bereichen von logischen über puzzle-typische Anordnungsprobleme bis hin zur Kartenfärbung existieren, um optimale Routen auf Karten zu finden und Prozesse zu planen. Erstaunlicherweise haben sich alle diese Probleme in dem Sinne als äquivalent erwiesen, dass wenn ein Polynomialzeitalgorithmus für eines von ihnen gefunden wird, dieser für alle anderen in einen Polynomialzeitalgorithmus umgewandelt werden kann - man könnte sagen, es gibt nur ein gemeinsames Gewinnen oder Verlieren.

Solche Probleme werden NP-vollständig genannt. ‚NP’ bedeutet: „nicht-deterministisch in Polynomialzeit“. Dieser Jargon bedeutet, dass das Problem in einer angemessenen Zeit gelöst werden könnte, wenn man einen Computer hätte, der eine beliebig große Anzahl von Lösungen auf einmal überprüfen könnte (das ist der nicht-deterministische Teil).

Du könntest meinen, dass dies eine ziemlich unrealistische Annahme ist, und das ist auch tatsächlich so. Es ist nicht möglich, einen solchen Computer zu bauen, da dieser beliebig groß sein müsste! Das Konzept einer solchen Maschine ist jedoch im Prinzip wichtig, da NP-vollständige Probleme anscheinend nicht in einer vernünftigen Zeitspanne ohne einen nicht-deterministischen Computer gelöst werden können.

Darüber hinaus wird diese Gruppe von Problemen als vollständig bezeichnet, weil obwohl die Probleme sehr unterschiedlich erscheinen - zum Beispiel, Kartenfäbung ist sehr unterschiedlich verglichen mit der Platzierung der Eiswagen – sich herausstellt, dass, wenn eine effiziente Lösung für ein Problem gefunden wird, die Methode auch angepasst werden kann, um jedes Problem dieser Gruppe zu lösen. Das ist es auch, was wir oben unter ‚gemeinsames Gewinnen oder Verlieren’ zum Ausdruck gebracht haben.

Es gibt Tausende von NP-vollständigen Problemen und ForscherInnen haben sie auf der Suche nach effizienten Lösungen für mehrere Jahrzehnte bisher ohne Erfolg verfolgt. Wenn für nur eines von ihnen eine effiziente Lösung gefunden worden wäre, hätten wir effiziente Lösungen für alle Probleme. Aus diesem Grund wird stark vermutet, dass es keine effiziente Lösung gibt. Aber zu beweisen, dass die Probleme notwendigerweise exponentielle Zeit benötigen, ist heute die herausragendste offene Frage in der theoretischen Informatik - möglicherweise in der gesamten Mathematik.

Weiterführende Literatur

Harels Buch Algorithmics stellt mehrere NP-vollständige Probleme vor und diskutiert die Frage, ob polynomielle Algorithmen existieren. In Dewdneys Turing Omnibus wird auch NP-Vollständigkeit diskutiert. Das Standardwerk im Bereich Computerwissenschaften zu diesem Thema ist Garey & Johnsons Computer and Intractivability, in dem mehrere hundert NP-vollständige Probleme, zusammen mit Techniken zum Nachweis der NP-Vollständigkeit, vorgestellt werden. Allerdings ist es ziemlich schwerfällig und eignet sich wirklich nur für InformatikspezialistInnen.