Weil hier vermutlich einige sind, die das interessiert: Ein Mathematiker namens Vinay Deolalikar behauptet, er habe das P-NP-Problem gelöst. Es handelt sich um ein wichtiges bis dahin ungelöstes Problem der Informatik, es ist ein Preis von 1 Mio. US-$ ausgesetzt.
P ≠ NP vielleicht gelöst
-
und wo ist der Link zu der Nachricht?
und wo ist der Beweis? -
und wo ist der Link zu der Nachricht?
und wo ist der Beweis?der kommt dann am 1.april :D:D:D
-
Tschuldigung, ich hab nicht an den Link gedacht.
Meldung bei heise -
ich ahbe den Link zum Beweis gefunden. Wer will kann sich das Paper ja mal druchlesen und auf Korrektheit checken.
http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf -
Hmm, das kam unerwartet.
Aber den Riemann knackt so schnell keiner.
Außerdem wäre ein Polynomialzeit-SAT-Solver viel cooler gewesen.
Schon scheiße, wenn das jetzt stimmt, dann müssen die ganzen Wikipedia-Artikel, die NPC-Probleme erwähnen geändert werden, ihr wisst schon, diese „man geht davon aus, dass es nicht effizient lösbar ist“-Formulierungen.
Achso, es bleibt übrigens noch was zu tun, wenn ihr solche Probleme mögt, wenn der Beweis stimmt, gibt es hier immer noch was zu klären:
L ⊆ NL ⊆ NC ⊆ P ⊂ NP ⊆ PSPACEL ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARYUnd vllt. ist je auch noch ein Wurm drin.
Zu Heise: Ich glaube nicht, dass das nur wegen des Preises überprüft werden will.
-
Doofe Frage, aber kann mir hier jemand das menschlich verständlich erläutern?
Ich versteh nur Bahnhof, mein Wissen reicht wohl nicht aus dafür
ps: Heises Artikel und Wikipedia versteh ich auch nich wirklich.
-
wo haktes denn, dere User erklärt dir das sicher.
Ich fand gerade bei heise haben sie es so erklärt, dass auch jemand, der kein Informatiker ist, das verstehen kann. -
Na toll, jetzt kann ich endlich ruhig schlafen. Seit Jahren hat mich dieses Problem beschäftigt und habe die fehlende Lösung für einen großen Verlust für die Welt der Kunst gehalten. Bin ich froh, dass sich die Erde wieder ruhig weiterdrehen kann.
Mal ehrlich, wenn interessiert das??? -
Na, also wenn rauskäme, dass P = NP ist und man dann eine Lösung finden würde, dann würde dies dfie Tehcnik revolutionieren, da man quasi jedes Problem in polynomieller Zeit lösen könnte.
Auch wenn der Beweis zunächst sehr mathematisch und theoretisch erscheint, so hat die Antwort doch großen Praxisbezug. Elektrotechnik und Informatik sind ja nichts anderes als Mathe.
Als Einstein den Npobelpreis für den Photoeffekt bekommen hat, haben sich bestimmt auch alle gedacht: Na toll, wen interessiert das. Ohne Photoeffekt gäbs keine LEDs, keine Solarzellen, ...
