Stell dir ein Schachbrett vor. Platziere zwei gegnerische Königinnen so darauf, dass sie sich nicht direkt angreifen können. Einfach? Gut, jetzt wiederhole den Vorgang und füge sechs weitere Königinnen hinzu. Kompliziert, aber möglich. Zum Schluss erweitere das Problem auf Bretter beliebiger Größe, mit beliebig vielen vorab festgelegten Königinnen. Das sogenannte „Problem der 1000 Königinnen“ ist nichts anderes als ein isoliertes Beispiel, um eine viel komplexere Übung zu erklären: „P versus NP“, in einem solchen Ausmaß, dass das Clay Mathematics Institute eine Million Dollar für den ersten positiven Beweis anbietet.
Die sieben Probleme des Jahrtausends
Es gibt einen sehr interessanten Wettbewerb, den man die „Sieben Probleme des Jahrtausends“ nennt. Er wurde im Jahr 2000 vom Clay Mathematics Institute ins Leben gerufen, mit dem Ziel, Antworten auf sieben klassische Probleme zu finden, die sich im Laufe der Jahre „widersetzt“ haben. Bisher ist das einzige Problem, das einen angemessenen Beweis erhalten hat, die „Poincaré-Vermutung“, entwickelt von dem russischen Mathematiker Grigori Perelman.
Das Institut zögerte nicht, ihm eine Million Dollar für seine Arbeit anzubieten, aber Perelman lehnte ab und sagte, sein Beitrag sei nicht größer gewesen als der des Mathematikers Richard S. Hamilton, der zuvor eine Lösung vorgeschlagen hatte. Ein weiteres der großen Probleme, das das Institut gelöst sehen möchte, ist das berühmte „P versus NP“, und um es zu verstehen, greift man am häufigsten auf das Schachspiel zurück:
Hat das nicht geholfen? Keine Sorge, mir hat es anfangs auch nicht viel genützt. P versus NP ist komplizierter, als ein paar Königinnen auf ein Brett zu werfen, und sein Ruf, unmöglich zu sein, ist mehr als gerechtfertigt. In sehr lockeren Worten (und ich sage „locker“ mit voller Aufrichtigkeit) können wir sagen, dass die Probleme, die mit P bezeichnet werden, einfach zu lösen und zu verifizieren sind, mit Algorithmen, innerhalb einer „polynomialen Zeit“.
Andererseits sind NP-Probleme leicht zu verifizieren, ob ihre Lösung richtig ist oder nicht, während das Finden viel Zeit und Mühe erfordert, mit bemerkenswerten Effizienzverlusten. Starke Beispiele für NP-Probleme sind Puzzles, Sudoku und auch das Minensuchspiel. Nun: Was würde passieren, wenn du den Schlüssel findest, um ein NP-Problem in polynomialer Zeit und mit großer Effizienz zu lösen?
Wenn dir das gelingt, wirst du beweisen, dass es keine Unterschiede zwischen P und NP gibt (P = NP), und das Clay Institute ((und nicht die University of St Andrews, wie bis zum Überdruss wiederholt wurde) wird eine Million Dollar in deine Richtung werfen, wahrscheinlich gefolgt von einem Nobelpreis und dem Hass von Krypto-Experten auf der ganzen Welt. Die meisten Experten neigen zu P ≠ NP, und ehrlich gesagt hängen viele Dinge davon ab (die bereits erwähnte Verschlüsselung ist eine davon). Aber wenn du es trotzdem versuchen willst... viel Glück. Du wirst es brauchen.
