Norbert Blum

Norbert Blum (* 1954 in Neustadt an der Weinstraße) ist ein deutscher theoretischer Informatiker und Hochschullehrer an der Universität Bonn.

Leben

Blum studierte ab 1974 Informatik und Mathematik an der Universität des Saarlandes, erhielt 1978 das Diplom und wurde 1981 bei Kurt Mehlhorn promoviert. Die Dissertation hatte den Titel: Eine Ω(n^4/3) [Omega-n] untere Schranke für die monotone Schaltkreiskomplexität von n-te Grad Convolution. 1988 habilitierte er sich in Saarbrücken (Habilitationsschrift: Fehlererkennung in kombinatorischen Schaltkreisen) und wurde im selben Jahr Professor in Bonn.

Er befasste sich unter anderem mit kombinatorischer Optimierung, Bioinformatik, formalen Sprachen und Compilerentwurf, Approximationsalgorithmen für NP-schwere Probleme, Algorithmen für Matching-Probleme und untere Grenzen für die Schaltkreis-Komplexität Boolescher Funktionen. Er veröffentlichte drei Lehrbücher über Informatik.

P-NP-Problem

Am 11. August 2017 veröffentlichte Blum einen Preprint, in dem er behauptet, die Lösung des P-NP-Problems gefunden zu haben in dem Sinn, dass die Komplexitätsklassen P und NP verschieden sind. Darin wird eine superpolynomiale (exponentielle) untere Schranke für nicht-monotone Schaltkreiskomplexität für das NP-schwere Cliquenproblem angegeben. Für monotone Boolesche Funktionen (das heißt solche ohne Negation) war eine superpolynomiale untere Schranke zuerst von Alexander Rasborow in den 1980er-Jahren angegeben worden, für nicht-monotone (die die Berechenbarkeits-Mächtigkeit von Turingmaschinen haben und für die der Nachweis einer solchen Schranke das P-NP-Problem lösen würde) war man aber seitdem erfolglos geblieben.

Blum baut seine Theorie auf einer Approximationsmethode von Rasborow auf, mit einer im Vergleich zu Rasborow abgeschwächten Distanzfunktion (Rasborow konnte mit seiner Distanzfunktion nur quadratische untere Schranken bei der nicht-monotonen Schaltkreiskomplexität beweisen), und auf Arbeiten von Christer Berg und Staffan Ulfberg (1999) sowie Kazuyuki Amano und Akira Maruoka (2004) bei deren Beweis einer exponentiellen unteren Schranke der monotonen Netzwerkkomplexität beim Cliquenproblem. Dass man mit Negation, also nicht-monotonen Booleschen Funktionen, die Schaltkreiskomplexität eines NP-schweren Problems nicht von exponentiell auf polynomial senken könne, war schon zuvor allgemein vermutet worden. Vor Blum hatten schon zahlreiche andere Wissenschaftler Beweise vorgeschlagen, die sich später als fehlerhaft herausstellten.

Am 30. August 2017 aktualisierte Norbert Blum den Preprint mit dem Kommentar, dass der Beweis fehlerhaft sei, und kündigte an, weitere Details zu dem Fehler nachzureichen. Am 11. Oktober 2017 veröffentlichte er seinen Fehler.

Schriften (Auswahl)

Bücher

• Eine Ω(n^4/3) [Omega-n] untere Schranke für die monotone Schaltkreiskomplexität von n-te Grad Convolution. 1981, DNB 820345733 ([Informatik-] Dissertation Universität Saarbrücken 1981, 32 Seiten, 21 cm).
• Theoretische Informatik. Eine anwendungsorientierte Einführung. De Gruyter Oldenbourg Wissenschaftsverlag, München/Wien 1998, ISBN 3-486-24279-2.
• Einführung in Formale Sprachen, Berechenbarkeit, Informations- und Lerntheorie. De Gruyter Oldenbourg, München/Wien 2006, ISBN 978-3-486-27433-2.
• Algorithmen und Datenstrukturen. Eine anwendungsorientierte Einführung. De Gruyter Oldenbourg, München 2004, ISBN 978-3-486-27394-6; 2. Auflage 2013, ISBN 978-3-486-71403-6.

Aufsätze

• Mit Martin Seysen: Characterization of all Optimal Networks for a Simultaneous Computation of AND and NOR. Acta Informatica, Band 21, 1984, S. 171–181.
• A Boolean Function Requiring 3n Network Size. Theor. Comput. Sci., Band 28, 1984, S. 337–345.
• An Area-Maximum Edge Length Trade-off for VLSI Layout. Information and Control, Band 66, 1985, S. 45–52 (und STOC (ACM Symposium on the Theory of Computing) 1984, S. 92–97).
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem. SIAM J. Comput., Band 15, 1986, S. 1021–1024.
• A New Approach to Maximum Matching in General Graphs. ICALP (International Colloquium on Automata, Languages, and Programming) 1990, S. 586–597.
• On Locally Optimal Alignments in Genetic Sequences. STACS (Symposium on Theoretical Aspects of Computer Science) 1992, S. 425–436.
• Mit Henning Rochow: A Lower Bound on the Single-Operation Worst-Case Time Complexity of the Union-Find Problem on Intervals. Inf. Process. Lett., Band 51. 1994, S. 57–60.
• Mit Y. Daniel Liang: Circular Convex Bipartite Graphs. Maximum Matching and Hamiltonian Circuits. Inf. Process. Lett., Band 56, 1995, S. 215–219.
• An O(n log n) Implementation of the Standard Method for Minimizing n-State Finite Automata. Inf. Process. Lett., Band 57, 1996, S. 65–59.
• Mit Robert Koch: Greibach Normal Form Transformation Revisited. Inf. Comput., Band 150, 1999, S. 112–118 (und STACS 1997, S. 47–54).
• Speeding Up Dynamic Programming without Omitting any Optimal Solution and Some Applications in Molecular Biology. J. Algorithms, Band 35, 2000, S. 129–168.
• On parsing LL-languages. Theor. Comput. Sci., Band 267, 2001, S. 49–59.
• On LR(k)-Parsers of Polynomial Size. ICALP, 2010, S. 163–174.
• Mit Matthias Kretschmer: Dynamic Programming. Evolutionary Distance. Algorithms Unplugged, 2011, S. 305–311.

Weblinks

• Webpräsenz von Norbert Blum