P!=NP womöglich bewiesen

Der Beweis für die mathematische Hypothese wäre eine Million Dollar wert und ließe Geheimdienst-Krypto-Strategen ruhig schlafen - möglicherweise ist er gefunden

Der bei den HP Labs angestellte Mathematiker Vinay Deolalikar will den Beweis für eine mathematische Hypothese gefunden haben, die 1971 kurz als P!=NP formuliert wurde. Hat das 103-seitige Dokument Recht, das sich jeder Interessierte bei Deolalikars Arbeitgeber herunterladen kann, dann würde das dem Mathematiker ein Preisgeld von einer Million US-Dollar garantieren.

Außerdem ließe der Beweis Geheimdienst-Strategen endlich ruhig schlafen, denn P!=NP besagt auch, dass trotz künftiger Quantencomputer noch erfolgreiche, von diesen Rechenmonstern nicht in kurzer Zeit lösbare Krypto-Strategien möglich sein müssen. Um das zu verstehen, muss man sich kurz die beiden Variablen ansehen: P steht für alle Probleme, die sich in polynomialer Zeit lösen lassen, deren Komplexität also nicht schneller als polynomial steigt. NP hingegen steht für "nichtdeterministische Polynomialzeit". Das sind Probleme, deren Lösung zwar "schwer" zu finden ist, wo sich die Richtigkeit der Lösung aber in Polynomialzeit ausrechnen lässt. Quantencomputer können alle P-Probleme, aber nur einige NP-Probleme in Polynomialzeit lösen, so viel weiß man - wie etwa die Primfaktorenzerlegung. Ist P also != NP, ist der Quantencomputer keine universelle Lösungsmaschine, es kann auch in Zukunft noch Geheimnisse geben.

Der Beweisversuch Deolalikars muss nun von der Forschergemeinde gründlich überprüft werden - erste Meinungen zu dem Paper sprechen von einer fundierten Arbeit, bleiben aber skeptisch, ob der Beweis wirklich vollständig erbracht wurde.