1000$ aus Beverly Hills für die Lösung eines Mathe-Problems

Oliver Friedmann, Doktorand in der Informatik an der LMU München, verteidigt nächsten Monat seine Dissertation. Darin enthalten ein Beweis, dass die "Zadeh-Regel" für die lineare Optimierung "exponentiell" ist, also sehr lange zur Problemlösung brauchen kann.
Oliver Friedmann (photo: Eddie Kim) 
 
Warum ist das bemerkenswert?
"Lineare Optimierung" beschreibt einen Typ von ausgesprochen wichtigen Rechenaufgaben, die in allen großen Planungsprozessen auftaucht.  Solche Probleme werden üblicherweise mit dem "Simplex-Verfahren" gelöst, das üblicherweise schnell arbeitet, manchmal aber auch ärgerlich lange braucht. Wie schnell das geht, hängt ganz entscheidend von einer Suchvorschrift ab, die in dem Verfahren die Einzelentscheidungen trifft, der "Pivot-Regel". Von den meisten Pivot-Regeln weiß man, dass sie bei manchen Rechenaufgaben sehr langsam sein können. Für die "Zadeh-Regel" wusste man das bisher nicht.
Vor dreißig Jahren, 1980, hat Norman Zadeh als Postdoc an der Stanford University einen Aufsatz über schwierige Beispiele für das Simplexverfahren geschrieben. Der Aufsatz ist nie in einer Zeitschrift erschienen, gehört aber zu den Klassikern der Mathematischen Optimierung. Um diese Zeit, als Zadeh noch nicht reich war, hat er ein Preisgeld von 1000$ ausgesetzt – für einen Beweis, dass die "least entered" Pivot-Regel, die in dem Aufsatz vorgeschlagen wurde, langsam kein kann – oder für einen Beweis des Gegenteils.  Die Ausschreibung des Preisgelds haben wir schriftlich, aus einem Brief an Victor Klee (1925-2007), Professor an der University of Washington in Seattle:  
Zadeh's Brief an Klee, (c) Günter M. Ziegler
Im Programm des Workshops am IPAM, dem "Institute for Pure and Applied Mathematics" an der UCLA (University of California at Los Angeles) ist für heute, Donnerstag, 20. Januar, 10 Uhr 30, ein Hauptvortrag von Oliver Friedmann  angekündigt, wo Friedmann seine Lösung des Problems vorstellen will: die Zadeh-Regel kann quälend langsam sein. Und Norman Zadeh will kommen, und einen Scheck von 1000$ für die Lösung des Problems überreichen.
Wer ist Norman Zadeh? 
Norman Zadeh ist ein Sohn von Lotfi Zadeh, der mit der Erfindung von "Fuzzy Logic" berühmt wurde. Der Sohn hat 1972 in Berkeley promoviert,  war dann Postdoc in Stanford, und aus dieser Zeit stammen seine Untersuchungen zur Laufzeit des Simplex-Verfahrens. Dann hat sich Zadeh aus der Mathematik entfernt, wurde als professioneller Pokerspieler sehr reich (er hat kürzlich seine Villa für über 16 Millionen Dollars verkauft) und ist jetzt seit vielen Jahren in der Industrie tätig, die Hochglanzbilder von schönen (nackten) Frauen produziert, unter anderem als Herausgeber von "Perfect10", einem Magazin, das mit expliziten Bildern von Frauen ohne Silikon in den Brüsten glänzt. Derzeit ist eine große Klage von Zadeh (der sich jetzt Norm Zada nennt) gegen Google anhängig: er hat Google verklagt, weil Google Links auf Webseiten mit Bildern herausgibt, die illegal kopierte Bildchen anbieten, die Zadeh gehören … also eine recht ungewöhnliche Mathematiker-Karriere.
Der Aufsatz von Oliver Friedmann ist ganz frisch, und natürlich noch nicht im Detail überprüft. Er ist aber gerade zur Vorstellung auf der renommierten IPCO-Konferenz 2011 angenommen worden. Bis zur endgültigen Überprüfung der Problemlösung soll ich, als ehemaliger Präsident der Deutschen Mathematiker-Vereinigung, erst einmal den 1000$-Scheck von Norman Zadeh in Obhut nehmen …..
 
Nachtrag, 21.1. abends in Los Angeles: 
Oliver Friedmann hat einen brillianten Vortrag gehalten, Zadeh ist wie angekündigt bekommen und hat den Scheck ausgestellt. Das Beweisfoto zeigt, von links nach rechts: Prof. David Avis (Kyoto/Montreal), Dr. Norman Zadeh (Perfect10), Oliver Friedmann (LMU München, mit dem Scheck) und Prof. Russ Caflish (IPAM-Director). 
Avis, Zadeh, Friedmann, Caflish (Photo: Eddie Kim)
Fotos: Eddie Kim, Delft

Veröffentlicht von

Professor für Mathematik an der Freien Universität Berlin, Leiter des “Medienbüros” der Deutschen Mathematiker-Vereinigung, Aktivist, Kommunikator, Sekttrinker, Gelegenheitsblogger, Kolumnist und Buch-Autor: "Darf ich Zahlen?" und "Mathematik - Das ist doch keine Kunst!".

Schreibe einen Kommentar




Bitte ausrechnen und die Zahl (Ziffern) eingeben