Mathekram

Mathematik rein und angewandt, erforscht und unterrichtet (ein Matheblog)

Archive for the ‘Millenniumsprobleme’ Category

Mal wieder ein bisschen Wind um P und NP

Posted by Modulix - August 27, 2010

Damit es nicht langweilig wird, gibt seit kurzem ein bisschen Aufregung um einen möglichen „Beweis“ der P/NP-Vermutung. Sogar der Spiegel berichtet darüber, ein Wiki existiert dazu ebenfalls bereits. Offenbar gibt es Zweifel an der Richtigkeit des Beweises. Allerdings wäre es ganz interessant zu erfahren, ob der Beweisansatz wenn schon nicht den Beweis liefert, so doch einen originellen Beitrag bedeutet, den nachzugehen lohnenswert wäre.

Terence Tao liefert in einem Kommentar zu einen Blog-Beitrag ein paar (mir allerdings unverständliche Anhaltspunkte):

„k-SAT (or more generally, any non-empty solution space of an NP problem) supports ppp distributions (by starting with the uniform distribution on \{0,1\}^n, and then returning some default solution if one falls outside the solution space). ppp supports seem to be close to something like a “polynomially computable image of a cube”, but I do not know the precise characterisation.

In order to support a pp distribution, the behaviour of the solution space in one of the variables (a terminal one in the pp factorisation) must depend on at most a polylog number of the other variables. Thus for instance the set EVEN of n-tuples (x_1,…,x_n) that add up to 0 mod 2 does not support pp, and more generally neither does a typical solution to a XORSAT problem. From the known clustering properties of SAT I can well believe that the same is also true for SAT in the hard phase, and it is likely that Deolalikar’s paper contained a proof of this fact.“

Advertisements

Posted in Mathematiker, Millenniumsprobleme, Netzwelt | Leave a Comment »

Bekommt eine Frau die nächste Fieldsmedaille?

Posted by Modulix - Juli 19, 2007

Vor einem Dreivierteljahr etwa schien sich eine Sensation zu ereignen:

Penny Smith, Mathematikerin an der Lehigh Universität in Betlehem (Pennsylvania, USA), veröffentlichte eine Arbeit auf dem allseits bekannten Preprint-Server ArXive, in welcher eine Lösung (genauer: der Nachweis der Existenz einer Lösung) der dreidimensionalen Navier-Stokes-Gleichungen behauptet wurde. Das Sensationelle besteht in der Tatsache, dass es sich dabei um eines der Millenniumsprobleme handelt, die das Clay-Institut auserkoren hatte. Wer ein solches Problem löst, hat schon geradezu einen Anspruch auf den Erhalt der Fieldsmedaille, weil diese Probleme unter den herausragenden Personen in der Mathematik als die Schlüsselprobleme gelten, die in der Mathematik einen entscheidenden Durchbruch bringen würden.

Würde also der Beweis von Penny Smith von der Fachwelt anerkannt werden, so könnte sie in 3 Jahren die Fieldsmedaille in Empfang nehmen, was insofern ungewöhnlich ist, als noch nie eine Frau den höchsten Preis der Mathematik erhalten hat.

Kurz nach Veröffentlichung ihrer Arbeit musste Frau Smith viel Kritik ertragen, und sie ließ erkennen, dass sie darunter auch zu leiden hatte. M.E. völlig zu Recht schrieb sie, dass es sich bei dem ArXive um einen Preperint-Server handelt, also etwaige Fehler, die sich in die Arbeit eingschlichen haben sollten doch mit etwas mehr Nachsicht zu behandeln sind. Das Thema der Wirkungsgeschichte ihrer Arbeit kann ausführlich mit zahlreichen Links hier nachgelesen werden.

Die Lösung des Navier-Stokes-Problems wäre nach dem Beweis der Poincare-Vermutung (für Dimension 3) durch Perelmann (der als scheuer Sonderling durch die Medien geistert) die zweite Lösung der insgesamt 7 Millenniumsprobleme.

Zu den 7 Millenniumsproblemen gehören:

  1. Die Birch-Swinnerton-Dyer-Vermutung (Gruppenstruktur elliptischer Kurven über \mathbb{Q})
  2. Die Hodge-Vermutung (aus der algebraischen Geometrie)
  3. Die Navier-Stokes-Gleichungen (in Dimension 3)
  4. Die P vs NP-Vermutung (Komplexität)
  5. Die Poincaré-Vermutung (in Dimension 3; für Dimension 4 gab es bereits eine Fieldsmedaille an M. H. Freedman 1986). Diese gilt als gelöst durch Perelmann.
  6. Die Vermutung über die Riemannsche Zetafunktion
  7. Die Frage nach der Existenz von Quanten-Yang-Mills-Theorien in Dimension 4.

Insgesamt bleibt abzuwarten, was aus der Arbeit von Penny Smith wird. Interessant bleibt, dass die Lösungskonstruktionen offenbar Ideen von Oskar Perron zurückgehen.

Posted in fieldsmedaille, Millenniumsprobleme, Partielle Differentialgleichungen | 2 Comments »