m
Übermensch
Nachrichten über die Verbesserung, Erweiterung und Ablösung des Menschen

P!=NP womöglich bewiesen

10.08.2010

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.

Anzeige
Cover

Die Form des Virtuellen

Vom Leben zwischen den Welten

Anzeige
Hellwach mit Telepolis
Anzeige
Cafe
Telepolis-Cafe

Angebot des Monats:
Kaffee und Espresso aus Nicaragua in der Telepolis-Edition für unsere Leser

Cover

Aufbruch ins Ungewisse

Auf der Suche nach Alternativen zur kapitalistischen Dauerkrise

Demokratie am Ende?

Wolfgang J. Koschnick analysiert den Niedergang der entwickelten parlamentarischen Parteiendemokratien. Das verbreitete Klagen über "die Politiker" und die allgemeine "Politikverdrossenheit" verstellt den Blick dafür, dass alle entwickelten Demokratien in einer fundamentalen Strukturkrise stecken.

bilder

seen.by

Mit dem Schalter am linken Rand des Suchfelds lässt sich zwischen der klassischen Suche mit der Heise-Suchmaschine und einer voreingestellten Suche bei Google wählen.

Tastenkürzel:

ctrl-Taste:
Zum Wechseln zwischen Heise- und Google-Suche

esc-Taste:
Verlassen und Zurücksetzen des Eingabe-Felds

Buchstaben-Taste F
Direkt zur Suche springen

SUCHEN

Mit dem Schalter am linken Rand des Suchfelds lässt sich zwischen der klassischen Suche mit der Heise-Suchmaschine und einer voreingestellten Suche bei Google wählen.

SUCHEN

.
.