Mathematik»Eine andere Welt«

Mathematiker streiten über Probleme, die jeden Computer überfordern. von 

Festplatte Computer Mathematik Rechner

Computer haben gewaltige Rechenkapazitäten – und doch braucht es für manche Matheaufgaben das menschliche Gehirn  |  © seraph/Photocase

DIE ZEIT: Hier in der indischen Stadt Hyderabad treffen die Mathematiker gerade zu ihrem Weltkongress zusammen. Im Vorfeld machte ein Beweis Furore , der zeigen sollte, dass P ungleich NP ist. Was bedeutet das, »P≠NP«?

Irit Dinur: P ist die Klasse der Probleme, für die wir einen effizienten Lösungsweg haben. NP ist die Klasse der Probleme, für die wir zwar keinen Weg kennen, aber deren konkrete Lösungen wir durchaus effizient überprüfen können…

Anzeige

ZEIT: …so wie das Problem des Handlungsreisenden, der auf kürzester Gesamtstrecke eine Anzahl von Städten besuchen soll. Es gibt bis heute keinen Rechenweg dafür…

Irit Dinur

Die Mathematikerin Irit Dinur ist Professorin für Informatik am Weizmann-Institut in Israel, an dem auch Nobelpreisträgerin Ada Yonath forscht. Dinurs Hauptforschungsgebiet ist die probabilistischen Überprüfung von Beweisen

Dinur: Genau. Aber wenn uns jemand eine Route gibt, können wir immerhin effizient überprüfen, ob diese korrekt ist.

ZEIT: Was heißt hier Effizienz?

Dinur: Die messen wir an der Rechenzeit. Es gibt ein paar harmlos aussehende Probleme, für deren Lösung man mehr Schritte braucht, als das Universum Atome hat. Ein Computer würde bis ans Ende der Zeit daran rechnen.

ZEIT: Aber Computer werden doch jedes Jahr besser.

Dinur: Dann machen wir die Aufgabe eben komplexer, und der Fortschritt ist wieder aufgezehrt. Das ist ein prinzipielles Problem.

ZEIT: Wir haben also einerseits P und andererseits NP…

Dinur: Und unter den NP-Problemen gibt es einige, die ganz unschuldig wirken, aber universell sind, weil sie alle anderen Probleme beinhalten. Die nennt man »NP-vollständig«, etwa die 3-Färbung eines Graphen. Könnte man zeigen, dass eines dieser universellen Probleme nicht zu P gehört, dann wäre P≠NP bewiesen.

ZEIT: Was aber, wenn P doch gleich NP wäre?

Dinur: Dann hätten wir eine sehr interessante Welt. Das würde bedeuten, dass man alles, was man überprüfen kann, auch erschaffen könnte: Ich bewundere ein Gemälde, überprüfe quasi seine Schönheit, könnte es also ebenso selbst malen.

ZEIT: Demnach würden alle Künstler und alle Mathematiker arbeitslos?

Dinur: Einen mathematischen Satz zu beweisen wäre nichts Besonderes mehr, nur noch ein sturer Automatismus. Die menschliche Fantasie, die in der Entdeckung eines Beweises steckt, wäre überflüssig. Darum glauben die meisten Mathematiker und Informatiker nicht an P=NP. Wir sind überzeugt, dass man andere Fähigkeiten braucht, um Kunst, Musik oder eben elegante Mathematik zu erschaffen, als sie nur nachzuvollziehen.

ZEIT: P≠NP ist eines der sieben Millenniumsprobleme, für deren Lösung je eine Million Dollar ausgesetzt ist. Vor zwei Wochen hat Vinay Deolalikar einen 100-seitigen Beweis präsentiert. Als sich den eine Handvoll Leute anschauten, fanden sie recht schnell Fehler. Seit 1971 wird daran geforscht. Ist P≠NP mit den aktuellen Mitteln der Mathematik überhaupt zu fassen?

Dinur: Es ist das wichtigste Problem der Theoretischen Informatik. Viele Menschen arbeiten daran, aber es ist keine Sache, die in den nächsten ein oder zwei Jahren erledigt wird. Schon von einer Menge leichterer Fragen wissen wir nicht einmal, wie wir sie lösen könnten.

Leserkommentare
    • Crest
    • 25. August 2010 18:19 Uhr

    Was sagt der Fachmann zur der These, dass mit P = NP dann auch gleich das 'Halteproblem' mit erschlagen wäre: Einen mathematischen Satz zu beweisen wäre nichts Besonderes mehr, nur noch ein sturer Automatismus. Die menschliche Fantasie, die in der Entdeckung eines Beweises steckt, wäre überflüssig.

    Hat die Dame das im Interview genau so formuliert?

    Herzlichst Crest

    Reaktionen auf diesen Kommentar anzeigen

    Darüber bin ich auch gestolpert, und kann mir die Aussage nicht erklären.

    Im Prinzip müssten wir über Familien von mathematischen Aussagen sprechen, deren Beweise polynomiell lang in der Länge der jeweiligen Aussage sind. Ob das in irgendeinem Kontext sinnvoll ist? Keine Ahnung.

    • ephes
    • 25. August 2010 21:26 Uhr

    @Crest

    Das Halteproblem ist nochmal deutlich schwerer, denn es ist ja nichtmal entscheidbar. Und zwischen "nicht entscheidbar" und np-vollständig ist jede Menge Platz. Schach (nxn-Brett) ist beispielsweise exptime-vollständig (entscheidbar aber schwerer als np-vollständig). Es gibt da einen ganzen Zoo von Komplexitätsklassen:

    http://qwiki.stanford.edu...

    Aber P = NP? ist halt die interessanteste Frage. Und "vernünftig langen Beweis finden" ist eben np-vollständig, während "vernünftig langen Beweis überprüfen" in p ist. Ganz verkürzt: Beschränkt sich das Finden von Problemlösungen auf ihre Überprüfung, oder ist das Finden ein grundsätzlich schwereres Problem?

  1. 2. Au ja

    @Crest

    Na das wäre mal toll, dann würde der Beweis, dass NP-Probleme deterministisch in polynomieller Zeit lösbar wären auch beweisen, dass alles lösbar wäre, der Beweis des Halteproblems somit hinfällig.
    Auch das Problem der natürlichen Sprache?
    Tolle neue Welt.

  2. Darüber bin ich auch gestolpert, und kann mir die Aussage nicht erklären.

    Im Prinzip müssten wir über Familien von mathematischen Aussagen sprechen, deren Beweise polynomiell lang in der Länge der jeweiligen Aussage sind. Ob das in irgendeinem Kontext sinnvoll ist? Keine Ahnung.

  3. Das koennte euch interessieren:
    http://cacm.acm.org/magaz...

    Was die Methode der Dame angeht, was bringt ein Algorithmus welcher nur zu 99.99% angeben kann ob ein Beweis richtig ist oder nicht? Selbst wenn es beliebig nah an 100% ran geht so ist trotzdem keine Gewissheit gegeben.

    Ist das nicht so aehnlich wie wenn 99.99% der Experten behaupten dass der Beweis richtig ist?

    Gruessle

    Reaktionen auf diesen Kommentar anzeigen

    Wenn es tatsächlich beliebig nah an 100% ran geht, dann ist der Beweis auch tatsächlich richtig, da der Grenzwert GLEICH 100% ist. Das wäre die mathematische Auffassung ihres sicher umgangssprachlich gemeinten "beliebig". ;)
    Aber natürlich kann man mit numerischen Näherungen nicht beliebig nah an die 100% kommen, sondern nur auf eine bestimmte Genauigkeit pro Rechenzeit.
    Das ist aber auch ein Grundproblem der Mathematik, die Beweisverfahren (insbesondere die Induktion, sowas kann keine andere Wissenschaft ernsthaft verwenden) basieren auf dogmatischen Aussagen, meist die Aussagen anderer Beweise. Aber man kann nie zu 100% wissen, ob nicht doch irgendwo schon ein Fehler in der Logik ist.
    Naja, die klaren Struckturen lassen meist "leichtes" (ich finds z.T. verdammt schwer...) überprüfen zu und auch die vielfältigen Anwendung lassen doch vermuten, dass das meiste stimmt.

  4. Wenn es tatsächlich beliebig nah an 100% ran geht, dann ist der Beweis auch tatsächlich richtig, da der Grenzwert GLEICH 100% ist. Das wäre die mathematische Auffassung ihres sicher umgangssprachlich gemeinten "beliebig". ;)
    Aber natürlich kann man mit numerischen Näherungen nicht beliebig nah an die 100% kommen, sondern nur auf eine bestimmte Genauigkeit pro Rechenzeit.
    Das ist aber auch ein Grundproblem der Mathematik, die Beweisverfahren (insbesondere die Induktion, sowas kann keine andere Wissenschaft ernsthaft verwenden) basieren auf dogmatischen Aussagen, meist die Aussagen anderer Beweise. Aber man kann nie zu 100% wissen, ob nicht doch irgendwo schon ein Fehler in der Logik ist.
    Naja, die klaren Struckturen lassen meist "leichtes" (ich finds z.T. verdammt schwer...) überprüfen zu und auch die vielfältigen Anwendung lassen doch vermuten, dass das meiste stimmt.

    Antwort auf "@1 und @2"
    • ephes
    • 25. August 2010 21:26 Uhr

    @Crest

    Das Halteproblem ist nochmal deutlich schwerer, denn es ist ja nichtmal entscheidbar. Und zwischen "nicht entscheidbar" und np-vollständig ist jede Menge Platz. Schach (nxn-Brett) ist beispielsweise exptime-vollständig (entscheidbar aber schwerer als np-vollständig). Es gibt da einen ganzen Zoo von Komplexitätsklassen:

    http://qwiki.stanford.edu...

    Aber P = NP? ist halt die interessanteste Frage. Und "vernünftig langen Beweis finden" ist eben np-vollständig, während "vernünftig langen Beweis überprüfen" in p ist. Ganz verkürzt: Beschränkt sich das Finden von Problemlösungen auf ihre Überprüfung, oder ist das Finden ein grundsätzlich schwereres Problem?

    • sevens
    • 25. August 2010 21:27 Uhr

    Ich finde das Interview sehr interessant und gelungen. Allerdings fehlt hier und da ein erklärender Einschub: Hätte ich beispielsweise nicht Informatik studiert, wüßte ich nicht unbedingt, was ich mir unter der Färbbarkeit von Graphen vorzustellen habe. Daß die Bekanntheit der Graphentheorie sonderlich weit über den Tellerrand der Infor-/Mathematikwelt hinausreicht, halte ich für unwahrscheinlich.

    Reaktionen auf diesen Kommentar anzeigen

    der Navigationsgeräte und Google Maps sollten die Grundzüge der Graphentheorie doch allegemein bekannt sein, oder? ;-)

  5. der Navigationsgeräte und Google Maps sollten die Grundzüge der Graphentheorie doch allegemein bekannt sein, oder? ;-)

    Antwort auf "Gutes Interview"

Bitte melden Sie sich an, um zu kommentieren

  • Artikel Auf einer Seite lesen
  • Schlagworte Mathematik | Affe | Computer
Service