Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Wunschartikel: Informatik: Glücksfall-Algorithmen

Eine neue Familie merkwürdiger Rechenverfahren wirft ein neues Licht auf die Grenze zwischen leichten und schweren Problemen und damit auf die härteste Nuss auf dem Gebiet der Komplexitätstheorie.
Glücksfall-Algorithmen
Warum sind einige Berechnungsprobleme so schwierig, andere dagegen recht einfach? Im Jargon der Komplexitätstheorie ausgedrückt, klingt die Frage längst nicht so albern: Ist P gleich NP? Für eine Antwort zahlt das Clay Mathematics Institute eine Million Dollar, jedenfalls wenn ein Beweis mitgeliefert wird (Spektrum der Wissenschaft 10/2008, S. 74 und 80).

Ein Beispiel möge erläutern, wie diffizil die Unterscheidung zwischen leicht und schwer im Einzelfall ist. Wir betrachten einen mathematischen Graphen, also eine Zusammenstellung von "Ecken" oder "Knoten" (durch Punkte dargestellt) und "Kanten" (Linien, die jeweils zwei Ecken miteinander verbinden).

Gibt es in diesem Graphen einen Weg, der jede Kante genau einmal durchläuft und dann zu seinem Ausgangspunkt zurückkehrt? Für jeden Graphen mit endlich vielen Kanten könnten wir diese Frage mit brute force ("roher Gewalt") beantworten: Wir probieren alle möglichen Wege der Reihe nach durch, ob sie die Bedingungen erfüllen. Es gibt aber ein erheblich besseres Verfahren: Leonhard Euler (1707 – 1783) bewies 1736, dass es einen solchen Weg (der heute "Euler-Kreis" heißt) genau dann gibt, wenn in jeder Ecke eine gerade Anzahl von Kanten zusammentrifft. Das ist leicht zu überprüfen und erspart einem die überaus mühsame erschöpfende Suche.

Nehmen wir jetzt denselben Graphen, stellen aber wie William Rowan Hamilton (1805 – 1865) eine etwas andere Frage: Gibt es einen Weg, der jede Ecke genau einmal durchläuft (einen "Hamilton-Kreis")? Diesmal gibt es keine Alternative zur rohen Gewalt. Bis heute kennt niemand eine Methode, die für jeden Graphen die richtige Antwort liefert und deutlich schneller arbeitet als die erschöpfende Suche.

Die beiden so ähnlich aussehenden Probleme sind so unterschiedlich schwierig wie nur denkbar. Woran liegt das? Gibt es einfach keine kurze Lösung für das Hamilton-Problem, oder sind wir bisher nur zu beschränkt, um sie zu finden? Die meisten Wissenschaftler sind von Ersterem überzeugt – aber bewiesen ist noch nichts. Und schließlich könnten jederzeit völlig neue, überraschende Ideen zur Lösung solcher Probleme auftauchen. Vor 1736 sah die Frage nach der Existenz eines Euler-Kreises schließlich auch schwer aus...

Kennen Sie schon …

Spektrum - Die Woche – Drohen im Winter Stromausfälle?

Deutschlands Stromnetz scheint am Limit – doch die Netzbetreiber halten die Gefahr von Stromausfällen derzeit für gering. Die Herausforderungen werden nach dem Winter jedoch nur noch größer. Außerdem in dieser Ausgabe: Sind blaue Räume besser als grüne? Und wie erschafft man unknackbare Funktionen?

Spektrum Kompakt – Unendlich

Seit Jahrtausenden fasziniert uns das Konzept der Unendlichkeit. Und noch immer steckt es voller Rätsel und Überraschungen.

Spektrum - Die Woche – Das ist eine regelrechte Hexenjagd

Lesen Sie in dieser Ausgabe, warum man Fledermäuse am besten in Ruhe lässt. Außerdem: was bisher über das Kawasaki-Syndrom im Zusammenhang mit Covid-19 bekannt ist und eine Reise in die Badlands.

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.