Wissenschaft Ist ein Jahrtausendproblem der Mathematik gelöst?
Seite 2/2:
Den "Nonsenstest" hat Deolalikars Beweis schon bestanden
Der Mathematiker Deolalikar behauptet dagegen, er habe ein NP-Problem gefunden, von dem er beweisen kann, dass es auf keinen Fall in P liegt. Erklären lässt sich sein Ansatz in ein paar Sätzen nicht, auch prominente Mathematiker geben zu, dass sie ihn nicht "mal einfach so" kommentieren können. Er macht Anleihen bei bislang weit auseinander liegenden Disziplinen – was auch zu erwarten ist, wenn alle nahe liegenden Versuche der letzten Jahrzehnte gescheitert sind.
In einem Wiki stecken nun die Experten der Komplexitätstheorie – zu diesem Zweig der theoretischen Informatik gehört das Problem – die Köpfe zusammen, um das 100-Seiten-Papier zu analysieren. Bislang ist aus diesem virtuellen Konklave weder weißer noch schwarzer Rauch aufgestiegen, bisher bekommt man nur Bauchgefühlaussagen. "Auf den ersten Blick ist es ein langes, gut geschriebenes Paper eines ernsthaften Forschers", mit diesen Worten adelte der angesehene Informatiker Richard Lipton den angeblichen Beweis. Mathematische Blogger bestätigen, dass die Arbeit "den Nonsenstest" besteht, also keinen offensichtlichen Unsinn eines Spinners darstellt.
Die vorherrschende Gefühlslage geht allerdings dahin, dass Deolalikar zwar einen interessanten Beitrag zur Lösung des Problems geleistet hat, dass allerdings die Löcher, Lücken und Irrtümer (von denen einige schon gefunden wurden) das Werk letztlich auseinanderfallen lassen werden. Der Informatikprofessor Scott Aaronson vom
Massachusetts Institute of Technology
(MIT) im amerikanischen Cambridge ist sogar bereit, darauf zu wetten: Wenn das Clay-Institut den Beweis tatsächlich akzeptiert und mit einer Million Dollar honoriert, dann legt er selber noch einmal 200.000 Dollar aus der eigenen Tasche drauf. "Wenn tatsächlich bewiesen wird, dass P ungleich NP ist", sagt Aaronson, "dann wird sich mein Leben so dramatisch ändern, dass die 200.000 Dollar nebensächlich sind."
Aber wie gesagt, das alles sind vorerst nur gefühlte Einschätzungen, die nicht viel mehr wert sind als die völlig aus der Luft gegriffene Prognose, die der deutsche Mathematiker Günter Ziegler in seinem vor
ein paar Monaten erschienenen Buch "Darf ich Zahlen?" gemacht hat: Das Problem werde 2012 von einem jungen Inder gelöst. In Zieglers Vision findet der Forscher allerdings eine dritte Antwort auf die Jahrtausendfrage: Sie sei beweisbar unbeweisbar.
Der Artikel wurde gegenüber der usprünglichen Version verändert (ein Fehler in der Definition der NP-Vollständigkeit).
Mehr zum Thema
Übersicht zu diesem Artikel
- Seite 1 Ist ein Jahrtausendproblem der Mathematik gelöst?
- Seite 2 Den "Nonsenstest" hat Deolalikars Beweis schon bestanden
Anzeige
- Datum 11.08.2010 - 19:02 Uhr
- Seite 1 | 2 | Auf einer Seite lesen
- Quelle ZEIT ONLINE
- Kommentare 53
- Versenden E-Mail verschicken
- Empfehlen Facebook, Twitter, Google+
- Artikel Drucken Druckversion | PDF
-
Artikel-Tools präsentiert von:
...ich hatte immer noch die (winzige) Hoffnung, dass P=NP gilt. Das wäre eine wirkliche Sensation gewesen!
Andersherum sind wir um ein Problem ärmer und um das Problem reicher, dass wir weiterhin viel Grips verschwenden müssen um NP schwere Probleme zu lösen.
Danke für den guten Artikel.
seien sie froh. Die Verschlüsselungstechnolgie beruht darauf, dass NP nicht P ist.
seien sie froh. Die Verschlüsselungstechnolgie beruht darauf, dass NP nicht P ist.
Danke sehr, Herr Drösser, für diesen interessanten Artikel. Leicht leserlich öffnen Sie einem die Tür zur doch eigentlich sehr interessanten Welt der Mathematik.
Halten Sie uns auf dem Laufenden. Ich wünsche Ihnen noch einen schönen Abend!
Also ich finds interessant, aber verstandne habe ich kein Wort!
Das muss nicht unbedingt am Autor liegen, sondern mag an meinem fehlenden mathematischen Verständnis liegen, aber mir ist das ganze vollkommen unklar!
Hat jemand ne Kindergarten Version für mich?
Also ich finds interessant, aber verstandne habe ich kein Wort!
Das muss nicht unbedingt am Autor liegen, sondern mag an meinem fehlenden mathematischen Verständnis liegen, aber mir ist das ganze vollkommen unklar!
Hat jemand ne Kindergarten Version für mich?
Angemessene Berichterstattung, auch wenn die Vereinfachungen ein wenig stark formuliert sind (es gibt offensichtlich, gerade wenn P!=NP, sehr viele verschiedene Grade von "Schwerheit" in der Komplexitätstheorie - allerdings eben eine erstaunliche Ordnung: fast immer ist die Schwierigkeit von zwei Problemen vergleichbar, also: eines ist schwerer als das andere. Das ist anders als, zum Beispiel, bei Musikinstrumenten. Es ist nicht offensichtlich, ob virtuoses Geigenspiel schwerer oder leichter als Pianospiel vergleichbaren Niveaus ist.)
Außerdem hat der letzte Absatz der ersten Seite einen schwerwiegenden Fehler, ich zitiere:
"Das Handlungsreisendenproblem gehört zu der interessanten Klasse von NP-Problemen, die sich durch eine seltsame Asymmetrie auszeichnen: Die Rechnung ist "schwer" – aber wenn einer eine vermeintliche Lösung anbietet, lässt sie sich auf "leichte" Weise überprüfen. Solche Probleme nennt man auch NP-vollständig..."
Das ist nicht korrekt. Alle NP Probleme lassen sich in P verifizieren. Die Eigenschaft der NP-Vollständigkeit für x sagt, dass alle anderen NP-Probleme auch, quasi als Emulation, in x berechnet werden können. NP-Vollständige Probleme sind sozusagen maximal schwer in NP.
Zunächst einmal freue ich mich über die lebendige Diskussion über meinen Text!
Und der Autor des Kommentars Nr. 3 hatte recht, bei der Definition des Begriffs der NP-Vollständigkeit ist mir einiges durcheinander geraten - ich habe die Sache korrigiert und das am Ende des Textes vermerkt!
Zunächst einmal freue ich mich über die lebendige Diskussion über meinen Text!
Und der Autor des Kommentars Nr. 3 hatte recht, bei der Definition des Begriffs der NP-Vollständigkeit ist mir einiges durcheinander geraten - ich habe die Sache korrigiert und das am Ende des Textes vermerkt!
So berauschend fand ich den Beitrag nicht. Anscheinend geht es darum den Eindruck zu gewinnen, dass Mathematiker Gefühle haben und, dass sie sich vorläufig nicht darauf einigen können, was für ein Ei genau gelegt wurde.
Da ich etwas, aber nicht übermäßig, fit in Komplexitätstheorie bin, versuche ich mich momentan selbst in das paper von Deolalikar einzuarbeiten. Was Deolalikar vorschlägt ist in der Tat nicht undramatisch, jedenfalls für jene, die von P = NP ausgegangen sind. Ich schlage vor, dass wir uns ein wenig gedulden und abwarten. Momentan hege ich äußerste Zweifel an dem Beweis, das am Rande.
Bis dahin wäre ich, wie mein Vorredner, über mehr erörternde Beiträge dankbar, gerne online, gerne zu verwandten Fragen. Die Printausgabe hat eine andere Leserschaft und damit anderen Interessen. Aber online scheint mir genug Raum für mathematische Spinnereien vorhanden zu sein.
Stimmt der Beweis, beweist er nicht nur, dass EIN NP- Problem nicht in P-Zeit lösbar ist, sondern dass sie es alle nicht sind.Denn:
"Wenn eines dieser Probleme in P liegt, dann gilt das für alle." Wenn es also eines der NP-Probleme nicht in P liegt, dann liegt jedes Problem nicht in P.
seien sie froh. Die Verschlüsselungstechnolgie beruht darauf, dass NP nicht P ist.
...sonst wären meine Master und Diplomarbeit offiziell als Zeitverschwendung enttarnt. Bei beiden habe ich seinerzeit Lösungswege für NP-schwere Problem behandelt.
in dem Moment wo der erste Quantencomputer läuft, brauchen wir ganz schnell neue Verschlüsselungsmethoden.
...sonst wären meine Master und Diplomarbeit offiziell als Zeitverschwendung enttarnt. Bei beiden habe ich seinerzeit Lösungswege für NP-schwere Problem behandelt.
in dem Moment wo der erste Quantencomputer läuft, brauchen wir ganz schnell neue Verschlüsselungsmethoden.
Die Mathematik ist so schön, faszinierend und leider so schwer.
Auch hier steht man als Laie nur staunend da. Versteht man überhaupt, worum es geht (ansatzweise), so ist man trotzdem noch fern davon, Inhalt und Bedeutung zu begreifen.
Mir wird schwindlig beim Versuch, auch nur einen möglichen Ansatz zu denken, wie man P = NP beweisen könnte. Das Gegenteil erscheint zunächst leichter, aber komischerweise überkommt mich da so ein Bauchgefühl, als wäre selbst der Nachweis eines NP ungleich P ein NP-Problem...
Noch eine Frage an die wirklich Versierten: Wie stellt man fest, ob ein konkretes Problem zu P oder NP gehört? Gibt es da allgemeine Aussagemöglichkeiten oder geschieht dies durch praktische Anschauung des konkreten Problems?
Wahrsprecher, tatsächlich: Für gewöhnlich muss man für ein gegebenes Problem einen Algorithmus angeben, der es in P oder NP oder irgendeiner anderen Schwierigkeitsklasse löst. Für bestimmte Fälle gibt es andere Möglichkeiten, meist per Reduktion: Das gegebene Problem auf ein anderes Zurückführen, von dem eine bestimmte Schwierigkeit schon bewiesen ist.
Und immer gilt dabei zu bedenken, dass P und NP nur zwei von sehr vielen Schwierigkeitsklassen sind, es gibt Probleme, die viel schwerer sind als NP und solche, die viel leichter sind als P.
PS: Bezugnehmend auf den Satz "...überkommt mich da so ein Bauchgefühl, als wäre selbst der Nachweis eines NP ungleich P ein NP-Problem...". Bitte nicht den Fehler machen und allgemeine Probleme in der "wirklichen" Welt, also etwa mathematische Beweise, mit P und NP assoziieren. Die Komplexitätstheorie bezieht sich auf sehr feste Rahmenbedingungen, die in vielerlei Hinsicht stark idealisiert sind und in denen der Agent, also das Rechenwerk, sehr dumm ist. Beweise in der Komplexitätstheorie wie der, den der Artikel oben zitiert, sind immer meta zu diesem Rechenwerk.
Eigentlich ist das Problem nicht so schwierig, man muss nur die wenige Begriffe wirklich verstehen.
Zunächst braucht man definieren, was überhaupt Berechenbarkeit bedeutet. Dazu wird die Turingmaschine definiert. Eine solche Maschine besteht aus einer Liste von Anweisungen und einem Bandspeicher. In einer Anweisung kann man immer eine Speicherzelle lesen, schreiben und zur vorherigen oder nächsten wechseln. Der Speicher ist unendlich groß. Die Annahme ist, dass dieses Modell alles beschreibt, was man tatsächlich automatisiert ausrechnen kann. (Nicht beweisbar, Church'sche These).
Dieses Modell gibt es nun in einer deterministischen Ausführung, in der in Abhängigkeit vom Inhalt einer Speicherzelle der nächste Schritt feststeht, und in einer nicht-deterministischen Variante.
Dieses Konzept des Nicht-Determinismus ist schwierig zu verstehen, da es in der Realität nicht existiert (außer vielleicht in der Quantentheorie, aber das ist ein anderes Thema). Eine solche Maschine kann in einem Schritt gleichzeitig in mehrere Folgezustände wechseln bzw. die richtige Aktion raten. Sie hält dann mit einem Ergebnis, wenn sie das in einem möglichen Berechnungspfad tut. Dadurch kann die Maschine quasi einen exponentiell großen Suchraum aufspannen und sich erst später für eine Möglichkeit entscheiden.
Wahrsprecher, tatsächlich: Für gewöhnlich muss man für ein gegebenes Problem einen Algorithmus angeben, der es in P oder NP oder irgendeiner anderen Schwierigkeitsklasse löst. Für bestimmte Fälle gibt es andere Möglichkeiten, meist per Reduktion: Das gegebene Problem auf ein anderes Zurückführen, von dem eine bestimmte Schwierigkeit schon bewiesen ist.
Und immer gilt dabei zu bedenken, dass P und NP nur zwei von sehr vielen Schwierigkeitsklassen sind, es gibt Probleme, die viel schwerer sind als NP und solche, die viel leichter sind als P.
PS: Bezugnehmend auf den Satz "...überkommt mich da so ein Bauchgefühl, als wäre selbst der Nachweis eines NP ungleich P ein NP-Problem...". Bitte nicht den Fehler machen und allgemeine Probleme in der "wirklichen" Welt, also etwa mathematische Beweise, mit P und NP assoziieren. Die Komplexitätstheorie bezieht sich auf sehr feste Rahmenbedingungen, die in vielerlei Hinsicht stark idealisiert sind und in denen der Agent, also das Rechenwerk, sehr dumm ist. Beweise in der Komplexitätstheorie wie der, den der Artikel oben zitiert, sind immer meta zu diesem Rechenwerk.
Eigentlich ist das Problem nicht so schwierig, man muss nur die wenige Begriffe wirklich verstehen.
Zunächst braucht man definieren, was überhaupt Berechenbarkeit bedeutet. Dazu wird die Turingmaschine definiert. Eine solche Maschine besteht aus einer Liste von Anweisungen und einem Bandspeicher. In einer Anweisung kann man immer eine Speicherzelle lesen, schreiben und zur vorherigen oder nächsten wechseln. Der Speicher ist unendlich groß. Die Annahme ist, dass dieses Modell alles beschreibt, was man tatsächlich automatisiert ausrechnen kann. (Nicht beweisbar, Church'sche These).
Dieses Modell gibt es nun in einer deterministischen Ausführung, in der in Abhängigkeit vom Inhalt einer Speicherzelle der nächste Schritt feststeht, und in einer nicht-deterministischen Variante.
Dieses Konzept des Nicht-Determinismus ist schwierig zu verstehen, da es in der Realität nicht existiert (außer vielleicht in der Quantentheorie, aber das ist ein anderes Thema). Eine solche Maschine kann in einem Schritt gleichzeitig in mehrere Folgezustände wechseln bzw. die richtige Aktion raten. Sie hält dann mit einem Ergebnis, wenn sie das in einem möglichen Berechnungspfad tut. Dadurch kann die Maschine quasi einen exponentiell großen Suchraum aufspannen und sich erst später für eine Möglichkeit entscheiden.
Wahrsprecher, tatsächlich: Für gewöhnlich muss man für ein gegebenes Problem einen Algorithmus angeben, der es in P oder NP oder irgendeiner anderen Schwierigkeitsklasse löst. Für bestimmte Fälle gibt es andere Möglichkeiten, meist per Reduktion: Das gegebene Problem auf ein anderes Zurückführen, von dem eine bestimmte Schwierigkeit schon bewiesen ist.
Und immer gilt dabei zu bedenken, dass P und NP nur zwei von sehr vielen Schwierigkeitsklassen sind, es gibt Probleme, die viel schwerer sind als NP und solche, die viel leichter sind als P.
PS: Bezugnehmend auf den Satz "...überkommt mich da so ein Bauchgefühl, als wäre selbst der Nachweis eines NP ungleich P ein NP-Problem...". Bitte nicht den Fehler machen und allgemeine Probleme in der "wirklichen" Welt, also etwa mathematische Beweise, mit P und NP assoziieren. Die Komplexitätstheorie bezieht sich auf sehr feste Rahmenbedingungen, die in vielerlei Hinsicht stark idealisiert sind und in denen der Agent, also das Rechenwerk, sehr dumm ist. Beweise in der Komplexitätstheorie wie der, den der Artikel oben zitiert, sind immer meta zu diesem Rechenwerk.
Auch wenn andere Komplexitätsklasen vom zugrundeliegenden Rechnermodell abhängen, die Aussage "P!=NP" ist unabhängig davon, ob eine Turing-Maschine, eine idealisierte Registermaschine oder ein modernes Produkt Intelscher Ingenieurskunst zugrunde gelegt wird. Wenn P!=NP gilt, wird auch ein Supercomputer NP-vollständige Probleme nicht in polynomiell begrenzter Zeit lösen können.
P.S. Christoph Drösser sollte vielleicht die vom Clay-Institut benannten offenen math. Fragen schlicht als Milleniumsprobleme bezeichnen, nicht als Jahrhundert- oder Jahrtausendprobleme. Nach Angaben des Instituts handelt es sich um eine Auswahl der wichtigsten Probleme zur Jahrtausendwende, mit dem Fokus auf klassischen Fragen. Das schliesst andere wichtige Probleme wie die mit dem Langlandsprogramm zusammenhängenden Vermutungen aus. Präziser wäre es, von Jahrtausendwendeproblemen zu sprechen.
Tau, natürlich, die Problemklassen sind insofern generalisierbar, als dass sie mit ähnlichen Maschinen ähnlich schnell entscheid- bzw. lösbar sind.
Aber: Mathematische Beweise sind im Allgemeinen nicht mit dieser Art simpler Rechenwerke (wie beispielsweise intel Supercomputer) entscheidbar, das Ergebnis dazu ist von Turing selbst: Es gibt keine Turingmaschine, die alle Turingmaschinen "simulieren" kann. Deshalb meta.
Natürlich gibt es, gerade in der Kombinatorik, einige wirklich ausgefeilte Beweise, die mit rechnerischen Methoden entschieden worden sind, etwa der Vierfarbsatz oder zuletzt die universelle Anzahl von Zügen zur Lösung eines Rubikscubes. Diese Probleme sind aber immer vor allem eines: Hochgradig endlich.
Mit anderen Worten: Seit Gödel 2 sind mathematische Beweise im allgemeinen keine Rechenaufgaben.
Auch wenn andere Komplexitätsklasen vom zugrundeliegenden Rechnermodell abhängen, die Aussage "P!=NP" ist unabhängig davon, ob eine Turing-Maschine, eine idealisierte Registermaschine oder ein modernes Produkt Intelscher Ingenieurskunst zugrunde gelegt wird. Wenn P!=NP gilt, wird auch ein Supercomputer NP-vollständige Probleme nicht in polynomiell begrenzter Zeit lösen können.
P.S. Christoph Drösser sollte vielleicht die vom Clay-Institut benannten offenen math. Fragen schlicht als Milleniumsprobleme bezeichnen, nicht als Jahrhundert- oder Jahrtausendprobleme. Nach Angaben des Instituts handelt es sich um eine Auswahl der wichtigsten Probleme zur Jahrtausendwende, mit dem Fokus auf klassischen Fragen. Das schliesst andere wichtige Probleme wie die mit dem Langlandsprogramm zusammenhängenden Vermutungen aus. Präziser wäre es, von Jahrtausendwendeproblemen zu sprechen.
Tau, natürlich, die Problemklassen sind insofern generalisierbar, als dass sie mit ähnlichen Maschinen ähnlich schnell entscheid- bzw. lösbar sind.
Aber: Mathematische Beweise sind im Allgemeinen nicht mit dieser Art simpler Rechenwerke (wie beispielsweise intel Supercomputer) entscheidbar, das Ergebnis dazu ist von Turing selbst: Es gibt keine Turingmaschine, die alle Turingmaschinen "simulieren" kann. Deshalb meta.
Natürlich gibt es, gerade in der Kombinatorik, einige wirklich ausgefeilte Beweise, die mit rechnerischen Methoden entschieden worden sind, etwa der Vierfarbsatz oder zuletzt die universelle Anzahl von Zügen zur Lösung eines Rubikscubes. Diese Probleme sind aber immer vor allem eines: Hochgradig endlich.
Mit anderen Worten: Seit Gödel 2 sind mathematische Beweise im allgemeinen keine Rechenaufgaben.
Bitte melden Sie sich an, um zu kommentieren