Mathematik

Mathematik: Wer dieses Problem löst, bekommt eine Million Dollar

Der Soziologe Max Weber sagte über Politik so schön prägnant: „Die Politik bedeutet ein starkes langsames Bohren von harten Brettern“. Wenn hingegen Mathematiker über harte Bretter sprechen, meinen sie Rechenaufgaben, die schwer zu lösen sind.

16.02.2017 09:00 Uhr / Tobias Fülbeck

Sie haben für solche Aufgaben auch einen Namen: NP-Probleme.  Die Lösung dieser Probleme ist leicht zu überprüfen, aber bis man die Lösung überhaupt erst einmal hat, dauert es Ewigkeiten. Zu unterscheiden sind sie von sogenannten P-Problemen, die mittels Algorithmus relativ easy zu lösen sind. Klingt kompliziert? Zu Recht.

Denn wir sind gerade mitten drin in der Komplexitätstheorie, einem Teilgebiet der theoretischen Informatik. Es lohnt sich hier zu forschen. Denn die Clay-Stiftung zur Förderung der Mathematik bietet demjenigen eine Million Dollar, der die folgende Frage beantworten kann. Ist P ungleich NP? Oder ist P gleich NP, was bedeuten würde, dass es für jedes dicke Brett letztlich einen Algorithmus gibt, der auch für P anwendbar ist? Das hieße: P und NP-Probleme sind – trotz aller Komplexität – letztlich das gleiche Kaliber. Klingt erstmal ziemlich weit weg vom Alltag, hätte aber womöglich große Auswirkungen für das Steuern von Maschinen und das Herstellen von Chips.

Nähern wir uns der Frage mit Beispielen.

Was ist ein P-Problem? Wenn Zahlen ihrer Größe nach sortiert werden, ist das ein Klassiker für P. Je mehr Zahlen es sind, desto länger dauert’s. Aber kompliziert ist was anderes.

Ein Klassiker für das NP-Problem ist das Beispiel des Handlungsreisenden. Stellen wir uns vor, ihr wollt eine Deutschland-Tour machen. Durch 49 Städte zwischen Rügen und Regensburg. Was ist die kürzeste Route zwischen den Städten, jede darf nur einmal besucht werden, Start und Zielort sind identisch? Wenn ihr die Lösung erst mal habt, könnt ihr die Kilometerzahl schnell im Taschenrechner überprüfen. Aber ihr habt erst mal Hunderte Quadrillionen möglicher Routen zu überprüfen.

Die große Milleniums-Frage ist, wir erinnern uns: Ist N ungleich NP? Die meisten Mathematiker argumentieren so, doch einen Beweis sind die schuldig.

Also: Ihr seid heiß auf die Lösung? Studiert Informatik. Stürzt euch in die Materie. Und sichert euch ein kleines Vermögen. Kann etwas dauern, aber dann seid ihr am Ende reich und weltberühmt.

(Text: Tobias Fülbeck)

Ganze Folgen nochmal ansehen

Nicht verpassen: Unsere Highlight-Videos

taff Livestream