Wichtigstes Informatikproblem soll gelöst worden sein


armin karner Seit vielen Jahrzehnten vergeblich gesucht: Eine Lösung für das Problem P versus NF. Nun steht ein weiterer möglicher Beweis zur Diskussion
Es ist eines der sieben Millenniums-Probleme, für die es je eine Million US-Dollar gibt. Ein deutscher Mathematiker hat einen neuen Beweis für P ungleich NP vorgelegt

Von Klaus Taschwer | derStandard.at

So richtig berühmt ist das sogenannte P-NP-Problem-Problem erst seit den 1970er Jahren und dem Anbruch des Computerzeitalters. Doch zumindest zwei der größten Denker des 20. Jahrhundert haben schon rund 20 Jahre früher Versionen davon formuliert: John Forbes Nash („A Beautiful Mind“) 1950 in einem Brief an die National Security Agency, in dem es um Kryptographie ging, sowie der aus Wien stammende Logiker Kurt Gödel sechs Jahre später in einem Schreiben an den Computerpionier John von Neumann.

Worum geht es bei diesem Problem, das eines der sieben Millienniums-Probleme ist, für deren Lösung das Clay Mathematics Institute im Jahr 2000 je eine Million US-Dollar auslobte? Es handelt sich dabei um eine Frage aus dem Gebiet der Komplexitätstheorie; etwas konkreter geht es um das Problem, wie schnell ein Computer Aufgaben bestimmter Komplexität lösen kann. Dabei unterscheidet man zwischen sogenannten P-Problemen und NP-Problemen.

weiterlesen

Advertisements

2 Gedanken zu “Wichtigstes Informatikproblem soll gelöst worden sein

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s