11.08.10 20:27 Uhr
 12.220
 

Indischer Mathematiker will Lösung für eins der Millennium-Probleme gefunden haben

Bei den so genannten Millennium-Problemen handelt es sich um äußerst komplexe mathematische Fragestellungen, die noch nicht bewiesen wurden. Eines von ihnen, die Poincaré-Vermutung, wurde 2002 gelöst. Der indische Mathematiker Vinay Deolalikar ist davon überzeugt, ein weiteres dieser Probleme gelöst zu haben.

Namentlich geht es um das P-NP-Problem, eine Fragestellung aus dem Bereich der Komplexitätstheorie. "P" und "NP" stellen hier verschiedene Komplexitätsklassen dar: "P" beinhaltet mathematische Probleme, die sich mit Hilfe von speziellen Algorithmen und einem Computer in endlicher Zeit lösen lassen.

In der "NP"-Klasse sind dagegen die Probleme zusammengefasst, die ein herkömmlicher Computer nicht lösen kann, weil die nötige Berechnungszeit exponentiell ansteigt. Deolalikars Lösungsansatz zielt darauf ab, zu beweisen, dass P ungleich NP ist. Daraus folgt, dass NP-Probleme generell unlösbar sind.


WebReporter: alphanova
Rubrik:   Wissenschaft
Schlagworte: Lösung, Theorie, Mathematik, Millenium-Problem
Quelle: www.wissenschaft-online.de

DAS KÖNNTE DICH AUCH INTERESSIEREN

London: Fettberg in Kanalisation soll in Biodiesel umgewandelt werden
Kunststoffe mithilfe von Enzym aus Algen synthetisierbar
Künstliche Intelligenz in der Lage, Alzheimer neun Jahre im Voraus zu berechnen

Diese News zu meinen Favoriten hinzufügen Beitrag abgeben

29 User-Kommentare Alle Kommentare öffnen

Kommentar ansehen
11.08.2010 20:27 Uhr von alphanova
 
+56 | -6
 
ANZEIGEN
Der Kern dieses Problems liegt in der NP-Klasse: Sind diese Probleme grundsätzlich nicht lösbar oder wurde nur der dazu benötigte Algorithmus noch nicht gefunden?
Die Prüfung des Beweises wird Jahre dauern.

In der Uni hatten wir auch mal zwei (Just-4-Fun) Vorlesungen über diese Millennium-Probleme. Verdammt harter Tobak.. Da qualmte am Ende jedem der Kopf.. inklusive dem Professor. Sein Kommentar:
"Mann Mann Mann, da rechne ich doch lieber lineare Gleichungen aus.. die tun einem nicht so weh"
Kommentar ansehen
11.08.2010 20:31 Uhr von Marknesium
 
+66 | -6
 
ANZEIGEN
jaja: mathematiker sind einfach die götter der nerds.

weder chemiker (ich^^) noch physiker, können dennen das wasser reichen^^
Kommentar ansehen
11.08.2010 21:00 Uhr von Lenzilein009
 
+6 | -5
 
ANZEIGEN
Ach das könnte ich sogar ;)

@Marknesium:
Genau meine Meinung^^
Kommentar ansehen
11.08.2010 21:03 Uhr von Gimpor
 
+6 | -12
 
ANZEIGEN
Kleiner Fehler: Es müsste in der Überschrift [...]für einEs der[...] heißen. Ansonsten klasse News und Plus =)
Kommentar ansehen
11.08.2010 21:08 Uhr von Muay_Boran
 
+27 | -3
 
ANZEIGEN
Ich hab gerade den ganzen: Text gelesen, aber wirklich kein Wort konnte ich mir merken, ich weiß nicht nach dem Abi schaltet mein Gehirn immer ab wenn ich Mathe lesen :O
Kommentar ansehen
11.08.2010 21:22 Uhr von derReisende
 
+21 | -0
 
ANZEIGEN
Kann das mal jemand genauer erklären...sofern dies bei Mathe-Problemen überhaupt möglich ist....???
Und wozu ist dies eigentlich von Bedeutung...??
Was kann so eine Lösung bewirken ??

( dies ist ernst gemeint )
Kommentar ansehen
11.08.2010 21:23 Uhr von siderun2
 
+1 | -4
 
ANZEIGEN
kleine Korrektur: Das gestellte Frage hat nichts direkt mit exponetieller Zeit zu tun sondern ist mit der Frage gleichzusetzen, ob man bei jedem Problem, bei dem man die Korrektheit einer vorgegebenen Lösung leicht überprüfen kann, auch die Lösung leicht auffinden kann - für Laien formuliert. Man müsste jetzt nämlich erklären, was das Wort "leicht" in diesem Zusammnhang bedeutet. Der indische Wissenschaftler hat nun wohl bewiesen, dass dem nicht so ist.
Kommentar ansehen
11.08.2010 21:31 Uhr von setech
 
+3 | -4
 
ANZEIGEN
Unfug! NP-Probleme sind ganz und gar nicht unlösbar. Hier verwechselt der Autor der News Komplexitätstheorie mit Berechenbarkeitstheorie.

Vereinfacht gesagt: Wenn P ungleich NP ist (und davon wird ausgegangen, bisher fehlt nur der Beweis), dann kann es für NP-Probleme keine Algorithmen geben, die das Problem effizient lösen können. Zumindest auf herkömmlichen Nicht-Quanten-Rechnern.

Die Probleme sind aber dennoch berechenbar: Für kleine Probleminstanzen sind sie sogar praktisch berechenbar, für größere Probleminstanzen zumindest theoretisch, lediglich der Zeitaufwand und die benötigten Resourcen werden schnell unpraktikabel.
Kommentar ansehen
11.08.2010 21:46 Uhr von setech
 
+3 | -3
 
ANZEIGEN
@siderun2: Nicht ganz. Wenn NP ungleich P ist, bedeutet das durchaus, dass es keine Algorithmen für ein NP-vollständiges Problem geben kann, die es (deterministisch) schneller als mit exponentiellem Aufwand schaffen.

Ebenso kannst du für eine gegebene Lösung für ein NP-vollständiges Problem nicht leicht rausfinden, ob sie korrekt ist. Da wir hier von Entscheidungsproblem sprechen, gibt es ohnehin nur zwei mögliche Lösungen: ja/wahr oder nein/falsch. Wäre das so, könnten wir einfach beide Lösungen in polynomieller Zeit durchtesten und P wäre gleich NP. :)

Es geht darum, dass man die Lösung für ein NP-vollständiges Problem dann polynomiell verifizieren kann, wenn man zusätzlich zu der Lösung noch einen "Beweis" mitliefert. Wenn ich nun also (wie auch immer) ein NP-Problem gelöst habe und dir meine Lösung samt "Beweis" liefere, kannst du in polyonomieller Zeit verifizieren, ob meine Lösung stimmt.

Der Knackpunkt steckt in diesem "Beweis". Der "Beweis" sagt dir (vereinfacht gesprochen) welche Rechenschritte du gehen musst, um für die gegebene Eingabe zu einem akzeptierenden Zustand zu gelangen. Wenn du diesen Weg kennst, brauchst du bis dahin nur polyonomiell viele Schritte. Kennst du meinen Beweis (und daher den Weg) nicht, dann musst du exponentiell viele Wege durchprobieren, um zum akzeptierenden Zustand zu gelangen.
Kommentar ansehen
11.08.2010 22:48 Uhr von DigitalForce1
 
+1 | -3
 
ANZEIGEN
wozu: das Ganze? Da kommen die nach 10 Jahren mit an, wo alles wieder läuft.

*grübel*
Kommentar ansehen
11.08.2010 22:49 Uhr von siderun2
 
+2 | -0
 
ANZEIGEN
@setech: "Nicht ganz. Wenn NP ungleich P ist, bedeutet das durchaus, dass es keine Algorithmen für ein NP-vollständiges Problem geben kann, die es (deterministisch) schneller als mit exponentiellem Aufwand schaffen."

Das sehe ich auch so, aber das entspricht nicht der Definition der Komplexitätsklasse NP, sondern ist ein Nebenprodukt.

"Ebenso kannst du für eine gegebene Lösung für ein NP-vollständiges Problem nicht leicht rausfinden, ob sie korrekt ist. Da wir hier von Entscheidungsproblem sprechen, gibt es ohnehin nur zwei mögliche Lösungen: ja/wahr oder nein/falsch. Wäre das so, könnten wir einfach beide Lösungen in polynomieller Zeit durchtesten und P wäre gleich NP. :)"

Sorry, da muss ich dir widersprechen. Nehmen wir das NP-vollständige Problem TSP (Problem des Handlungsreisenden). Sicher ist es ein Entscheidungsproblem, ob eine bestimmte vermutete Lösung auch wirklich die Lösung darstellt und du kannst tatsächlich in polynomialer Zeit verifizieren, ob dies die Lösung ist, oder ob nicht. Aber wenn sie es nicht ist, was hast du dann gewonnen? Die Lösung des TSPs sicher nicht, weil du ja im ungünstigen Fall jetzt nur weisst, welche potenzielle Lösung, unter sehr vielen, ausscheidet. Du müsst also im worst case sehr viele Entscheidungsprobleme lösen (exponetiell viele) um ein NP-vollständiges Problem zu lösen, falls NP ungleich P ist.

"Es geht darum, dass man die Lösung für ein NP-vollständiges Problem dann polynomiell verifizieren kann, wenn man zusätzlich zu der Lösung noch einen "Beweis" mitliefert"

Naja, was immer du unter "Beweis" verstehen willst. Es ist immer eine deterministische Turingmaschine möglich, die eine vorgegebene Lösung eines Problems aus NP in polynomialer Zeit verifiziert. Wenn du den Korrektheitsbeweis des Turingprogramms, welches Lösungen untersucht als Beweis bezeichnen möchtest? Mir ist keine Definition der Klasse NP bekannt, in der ein Beweis eigegeben würde, sondern umgekehrt wird bei der Überprüfung der Lösung ein Beweis für die Korrektheit (auf Wunsch) ausgegeben und generiert, zumindest wird der Beweis vom Programm selbst geführt. Der Algorithmus hinter dem Turingprogramm ist also ein für ein ganz spezielles Problem geschriebenes Beweisprogramm. Und so speziell ist es auch wieder nicht, es ist insofern sogar ziemlich universell, als man jedes beliebige NP-vollständige Problem auf das TSP oder das 3-SAT-Problem abbilden kann.

Vielleicht kannst du mir eine Quelle geben, wo du das mit dem "Beweis" her hast. Die würde ich gerne mit eigenen Augen sehen.
Kommentar ansehen
11.08.2010 22:54 Uhr von Near
 
+1 | -0
 
ANZEIGEN
Okay Als ich das gelesen habe kam ich mir als mathematisch unbegabter Mensch einen Moment lang unglaublich dumm vor. xD

Nichtsdestotrotz eine gut geschriebene News und ein recht interessantes Thema.
Kommentar ansehen
11.08.2010 23:18 Uhr von erichmiller
 
+0 | -0
 
ANZEIGEN
Lenzilein009: nixht böse sein. Erfinden oder die Nadel im Heuhaufen finden. Das ist der Clou.
Kommentar ansehen
11.08.2010 23:43 Uhr von alexanderr
 
+1 | -1
 
ANZEIGEN
mein chemielehrer sagte einst:
die mathematik ist die hure der naturwissenschaft :)
Kommentar ansehen
12.08.2010 00:00 Uhr von NetCrack
 
+0 | -3
 
ANZEIGEN
Die Lösung soll sein das es keine Lösung gibt? Ähhhm ok.
Kommentar ansehen
12.08.2010 00:01 Uhr von erichmiller
 
+0 | -0
 
ANZEIGEN
alexanderr: ein wahres wort
Kommentar ansehen
12.08.2010 00:06 Uhr von erichmiller
 
+0 | -0
 
ANZEIGEN
Matthias1979: nun mal langsam. bist du der messias?. immer die füsse stillhalten. wär gut. oder die welt retten.
Kommentar ansehen
12.08.2010 00:52 Uhr von setech
 
+0 | -0
 
ANZEIGEN
@siderun2 - Teil 1: "Sicher ist es ein Entscheidungsproblem, ob eine bestimmte vermutete Lösung auch wirklich die Lösung darstellt und du kannst tatsächlich in polynomialer Zeit verifizieren, ob dies die Lösung ist, oder ob nicht."

Du unterliegst einem grundlegenden Missverständnis: Ist ein Entscheidungsproblem NP-vollständig, dann bedeutet das unter der Annahme P ungleich NP, dass du zur Lösung dieses Entscheidungsproblems (im worst case) exponentielle Zeit brauchst. Was du hier als "verifizieren, ob dies die Lösung ist oder ob nicht" bezeichnest, ist keine Verifizieren, sondern das Lösen des eigentlichen Entscheidungsproblems!

Dein Entscheidungsproblem "sag mir für eine bestimmte Tour ob sie optimal ist" ist eigentlich nicht geläufig, üblicherweise lautet die Entscheidungsvariante des TSPs "gibt es eine Tour mit Kosten <= b".

Aber bleiben wir bei deiner Variante: Wenn sich das Entscheidungsprobleme "Ich behaupte, diese Rundreise hier ist optimal, stimmt das?" von einer deterministischen Turingmaschine in Polynomialzeit lösen ließe, dann wäre dieses Entscheidungsproblem gemäß Definition nicht NP-vollständig.

"Aber wenn sie es nicht ist, was hast du dann gewonnen? Die Lösung des TSPs sicher nicht, weil du ja im ungünstigen Fall jetzt nur weisst, welche potenzielle Lösung, unter sehr vielen, ausscheidet. Du müsst also im worst case sehr viele Entscheidungsprobleme lösen (exponetiell viele) um ein NP-vollständiges Problem zu lösen, falls NP ungleich P ist."

Von welchem NP-vollständigen Problem, zu dessen Lösung ich viele Entscheidungsprobleme lösen müsste, redest du hier?

Du meinst doch nicht etwa das Auswertungsproblem, das fragt "Was ist die beste Rundreise?". Denn ein Auswertungsproblem kann gemäß Definition gar nicht NP-vollständig sein, weil es ein Auswertungsproblem und kein Entscheidungsproblem ist!

Ich gebe dir ein anderes Beispiel, bei dem die Entscheidungsvariante "natürlicher" wirkt als beim TSP und es daher unwahrscheinlicher macht, dass du im Hinterkopf immer die Auswertungsvariante hast: Das 3-CP. Das 3-CP fragt bei gegebenem Spielplan und der Anwendung der 3-Punkte-Regel (wie in der Fußballbundesliga): Kann Mannschaft X noch Meister werden? 3-CP ist NP-vollständig.

Eine mögliche Anfrage würde nun lauten "Kann Mannschaft X noch Meister werden?" und die mögliche richtige Antwort heißt nun "ja" oder "nein". Ich sage dir jetzt "Mannschaft X kann noch Meister werden! Bitte verifiziere meine Lösung."

Würde diese Verifikation nun ohne den in meinem letzten Beitrag angesprochenen "Beweis" in polynomieller Zeit funktionieren, dann könntest du dir selbst die Antwort "X kann noch Meister werden" geben und hättest in polynomieller Zeit dein NP-vollständiges Entscheidungsproblem gelöst, was unter der Annahme P!=NP aber nicht geht.

(Teil 2 wegen Zeichenbeschränkung im nächsten Beitrag)

[ nachträglich editiert von setech ]
Kommentar ansehen
12.08.2010 00:53 Uhr von setech
 
+0 | -0
 
ANZEIGEN
@siderun2 - Teil 2: (Teil 2 wegen Zeichenbeschränkung)

"Es ist immer eine deterministische Turingmaschine möglich, die eine vorgegebene Lösung eines Problems aus NP in polynomialer Zeit verifiziert."

Ein Entscheidungsproblem hat doch nur zwei Lösungen: Ja oder nein. Noch einmal: Wenn ich einfach mal "ja" behaupte und mir das polynomiell von einer DTM ohne weiteren "Beweis" verifizieren lassen kann, dann habe ich das Entscheidungsproblem in Polynomialzeit gelöst.

"Wenn du den Korrektheitsbeweis des Turingprogramms, welches Lösungen untersucht als Beweis bezeichnen möchtest?"

Nein, sondern Folgendes: Eine NTM hat in jedem Schritt die Möglichkeit, sich nicht-deterministisch zwischen verschiedenen Folgezuständen zu entscheiden und wählt, falls die Eingabe anzunehmen ist, denjenigen, der auf dem Weg zu einem akzeptierenden Zustand liegt. Wenn du eine DTM konstruieren willst, die das gleiche tut, wie die NTM, dann sorgt dieser Umstand für ein exponentielle Vermehrung der Zustände.

Wenn du hingegen aber weißt, welche Auswahl die NTM trifft, dann konstruierst du dir bei deiner Verifikations-DTM nur die Zustände, für die sich die NTM auch tatsächlich entschieden hat.

Du kannst es auch algorithmisch betrachen: Du nimmst einen randomisierten Algorithmus, der eine anzunehmende Eingabe im Falle eines NP-vollständigen Problems mit Wahrscheinlichkeit > 0 annimmt. Nun derandomisierst du den Algorithmus, indem du du ihm die von ihm benötigten Zufallsbits im Vorfeld als Bitvektor (fester Länge) mitgibst. Ist die Eingabe anzunehmen, dann wird dieser Algorithmus für mindestens einen dieser Bitvektoren die Ausgabe "Ja" zurückgegeben. Kennst du den Bitvektor nicht, muss du im worst case alle exponentiell vielen möglichen Bitvektoren durchprobieren.

Gibst du den richtigen Bitvektor aber als "Beweis" mit, reicht dir ein Durchlauf mit diesem Bitvektor zur Verifikation.

Weil du nach den Quellen fragst: Als Bücher habe ich hier "Komplexitätstheorie" und "Theoretische Informatik - Eine algorithmenorientierte Einführung" (beide von Ingo Wegener) hier. Falls du was online suchen magst: Meine Grundvorlesung in theoretischer Informatik fand im Sommersemester 2004 nach diesen Folien statt (leider keine Übersicht, aber Komplexitätstheorie kam in der Vorlesung damals zuerst):

http://ls2-www.cs.uni-dortmund.de/...

Ein alternativer Foliensatz von einem anderen Lehrstuhl zum gleichen Thema findest du hier:

http://zeus.cs.uni-dortmund.de/...
Kommentar ansehen
12.08.2010 03:44 Uhr von TausendUnd2
 
+2 | -2
 
ANZEIGEN
Ja super News...
Mensch Leute tut doch nicht so, als ob ihr das verstehen würdet! Die News von Alphanova sind immer so verfasst, dass nur Experten auf dem jeweiligen Gebiet überhaupt etwas verstehen! Ich hab ja nix gegen solche Physik-News, aber du müsstest deine News mehr vereinfachen, sodass auch "Normalos" sie verstehen! Ja gibt mir ruhig eure "-", aber ich würde darum wetten, dass nicht mal 2% der ShortNews-Nutzer etwas mit dieser News anfangen können!
Kommentar ansehen
12.08.2010 03:58 Uhr von setech
 
+1 | -0
 
ANZEIGEN
@TausendUnd2: Der Stoff ist Bestandteil des Grund- bzw. Bachelor-Studiums der Informatik an der Uni. Bei uns in Dortmund macht man das im vierten Semester.

Ich gehe mal davon aus, dass auch Studierende anderer Fächer, die Informatik im Nebenfach haben, das Thema häufig vorgesetzt bekommen, da es in der Informatik ziemlich zentral ist.

Geh also mal davon aus, dass der ein oder andere, den du im Internet triffst, den Kram vielleicht zufällig studiert und nicht nur den zugehörigen Wikipedia-Artikel gelesen hat. :)
Kommentar ansehen
12.08.2010 07:23 Uhr von Jacques_Mesrine
 
+0 | -6
 
ANZEIGEN
oha, alles leute hier, die stolz behaupten:

"höy, ich hab auch mal studiert" so lächerlich...vom feinsten.
Kommentar ansehen
12.08.2010 08:01 Uhr von francodimo
 
+0 | -2
 
ANZEIGEN
Schwerwiegendes Problem Sollte der Inder Recht haben, ist mein ganzes Leben über den Haufen ...
Oh Gott, wenn wirklich P > NP sein sollte ... dann ist alles zu Ende.
Was soll ich denn nun machen?
Kommentar ansehen
12.08.2010 08:54 Uhr von George Taylor
 
+0 | -2
 
ANZEIGEN
Blödsinn²: "In der "NP"-Klasse sind dagegen die Probleme zusammengefasst, die ein herkömmlicher Computer nicht lösen kann"

Und wie sieht es in 50 Jahren aus? Ich kontere mit dem Mooreschen Gesetz und sage: jedes Mathematische Problem ist irgendwann mit dem herkömmlichen Computer lösbar.
Kommentar ansehen
12.08.2010 09:17 Uhr von dazw
 
+3 | -0
 
ANZEIGEN
Ich hätte schon viel früher mit dem Artikel gerechnet.
Der Beweis wurde schon am 6.08.2010 eingereicht und es war vorgestern schon auf Heise zu lesen.

@George Taylor:

Auch wenn in 50 Jahren derzeitige NP-Probleme effektiv gelöst werden können, so wird es immer wieder neue NP-Probleme geben. Es ist ja nicht so, als ob die Menge P und NP immer gleich ist. P ist ja eine Teilmenge von NP und jetzt wurde vermutlich bewiesen, dass NP keine Teilmenge von P und demnach P != NP ist. Außerdem ist das ganze ja ein theoretischer Ansatz und man wird immer wieder NP-Probleme finden können ;)

Das beste Beispiel für ein NP-Problem ist "Der Handlungsreisende" http://de.wikipedia.org/...

Die Berechnung der Route steight exponentiell mit der Anzahl der Städte.

Ein Beispiel für ein P-Problem wäre das Suchen in einem Telefonbuch. Man schlägt es in der Mitte auf und nimmt dann immer eine der Hälften und teilt diese wieder. Bis man den Namen gefunden hat.
Hat das Telefonbuch plötzlich doppelt so viele Seiten, braucht man es nur 1x mehr teilen. Also steigt der Aufwand für die doppelte Menge an Seiten nicht exponentiell.

[ nachträglich editiert von dazw ]

Refresh |<-- <-   1-25/29   -> -->|
Diese News zu meinen Favoriten hinzufügen Beitrag abgeben


Copyright ©1999-2017 ShortNews GmbH & Co. KG

Die News auf dieser Website werden eigenverantwortlich von Nutzern erstellt. Die Shortnews GmbH & Co. KG nimmt keinen redaktionellen Einfluss auf die Inhalte.

impressum | agb | archiv | usenet | zur mobilen Ansicht
SCHLIESSEN

Willst Du die Seite wirklich verlassen?


DAS KÖNNTE DICH AUCH INTERESSIEREN

Die Mitwirkung der AFD in den parlamentarischen Gremien soll sabotiert werden.
Tegernsee: Ermittlungen wegen Urkundenfälschung gegen AfD-"Prinz"
Herr Altmaier (CDU - Kanzleramtschef) empfiehlt statt AFD besser nicht zu wählen


...oder unseren und keine aktuellen News mehr verpassen?