Ist P=NP?

http://scienceblogs.de/mathlog/2017/08/15/ein-gegenbeispiel-zu-pnp/ Die verlinkte Arbeit (Das Arxiv Paper A Solution of the P versus NP Problem by Norbert Blum) ist kein wissenschaftliches Paper was sich mit dem P=NP Problem beschäftigt, sondern es ist ein Witz-Paper was mit Scigen erzeugt wurde, und was wohl lustig sein soll. Schon in der Einleitung wird großspuring von einem CNF/DNF-Approximator gesprochen. CNF heißt übersetzt soviel wie konjunktive Normalform, ein Prinzip aus der Mathematik was ganz sicher nicht im Stande ist das P=NP Problem zu lösen. Vielleicht ein kleiner Exkurs dazu. Beim NP-Problem geht es um sogenannte np-harte Probleme, also Aufgaben die ähnlich wie das Rucksackproblem sehr viel Rechenzeit benötigen. Die Frage was die theoretische Informatik beschäftigt lautet, ob es Algorithmen gibt, die weniger Rechenzeit bedürfen. Und wie man schon ahnt geht es also um Turing-Maschinen. Turing-Maschinen lassen sich jedoch nicht mathematisch sondern nur innerhalb der Informatik definieren. Dort verwendet man üblicherweise Compiler, Finite-State-Maschines und Quantencomputer.

Meiner Meinung nach kann man das P=NP Problem nur lösen, wenn man es erweitert zum AI-Complete Problem. Also Probleme definiert, die natürliche Intelligenz verwenden. Dafür jedoch hat nochnichtmal die Informatik eine anerkannte Definition sondern man muss weitere Wissenschaften (speziell die Psychologie) bemühen. Hier der Plan:

Mathematik -> Informatik -> Psychologie

Was das Paper von Norbert Blum macht ist, sich auf die Mathematik zu beschränken, also mit ein wenig Formeln umstellen die Sache abzuhandeln. Das kann nur schiefgehen, es ist so, als wenn man mit einer Zahnbürste das Bad reinigt. Vermutlich wird sich Blum ins Fäustchen lachen, wenn er daran denkt wie sich arglose Arxiv-Leser damit wissenschaftlich auseinandersetzen.

Advertisements

Spam Filter mit Bayes Formel?

[1] Der Satz von Bayes wird von einigen Mathematikern nach wie vor als Weltformel identifziert, also als ein Wunderelexier mit dem sich jede Art von Problem lösen lässt. Und in der Tat hat die Wahrscheinlichkeitsrechnung Vorteile wenn man umfangreiche Datenbestände in Spam und Non-Spam unterteilen will. Allerdings darf bezweifelt werden, dass in der beschriebenen Form im OP die Implementierung einer Software Sinn machen würde. Nur mal als Erläuterung was der Bayes Satz ist: es handelt sich um eine kleinere Formel die sich in 2 Zeilen C-Code programmieren lässt, wenn das jetzt der komplette Spam-Filter sein soll, wie gut kann der sein? Richtig, um die Sache professioneller anzugehen braucht man wesentlich mehr. Wie wäre es beispielsweise mit einer „Finite State Machine“ wo über mehrere Ebenen verteilt ein Parser implementiert wird? Im Layer1 könnte man alle E-Mails von einem bestimmten Absender ausfiltern, in Layer2 dann die mit den Stop-Words, in Layer3 die mit den vielen Links usw. Mit Wahrscheinlichkeitsrechnung hat das nicht viel zu tun, eher mit Modellierung als Automaton. Generell wird in der Schulmathematik der Stochastik viel zu viel Bedeutung beigemessen.

Chaotische Systeme und „maneuver automaton“

[1] Die Modellierung von chaotischen Systemen stellt nach wie vor eine Herausforderung für die Mathematik da. Allerdings nur für eine veraltete Mathematik, die noch noch mit Rechenschiebern arbeitet. Nimmt man den modernen Automatenbegriff von Turing zum Ausgangspunkt kann man sogenannte „maneuver automaton“ konstruieren https://asco.lcsr.jhu.edu/papers/FlObKo2012.pdf. Es handelt sich dabei um hybride Automaten, die chaotische interdependente Systeme beschreiben (wie den eingangs erwähnten umgekippten Wasserteich). Die Modellierung solcher Mannöver-Automaten (keine Ahnung, ob das die richtige Übersetzung ist) ist nicht ganz simpel, aber für gute Mathematiker sollte es möglich sein. Man erhält ein sehr eleganten formales System, das sich gut in eine Programmiersprache wie Python übertragen lässt.

Modellierung von Schaukeln

[1] Laut dem Podcast wurde das Schaukeln (swing up task) als Differentialgleichung 2. Ordnung modelliert. Damit sind linerare Gleichungen gemeint, die 2 Inputvariablen besitzen. Differentialgleichungen sind ein Konzept was früher auf Analogcomputern verwendet wurde. Besser sind turing-mächtige Modelle (Finite State Machine). Soetwas benötigt man beispielsweise wenn man einen Zeichentrickfilm a la Pixar modellieren möchte. Dennoch war der Podcast ein guter Einstieg ins Thema und es es ist schön dass das Thema auf Deutsch aufgegriffen wurde. Warum das Karlsruher Institut für Mathematik noch mit Analog-computern arbeitet und nicht schon etwas moderner aufgestellt ist schade.

[2] Der obige Podcast mit dem Thema Schaukeln war noch einer von den besseren Folgen. Hört man in die Episode #111 des „Modelansatz“ Podcast hinein wo es um Mathematik ganz allgemein geht, sträuben sich die Nackenhaare auf über soviel Unverständnis der Mathematik gegenüber. Man kann es nicht anders sagen, aber die Episode hat fast nichts mit Mathematik zu tun, stattdessen werden dort gesellschaftliche Dinge besprochen wie Stuttgart 21, die Vermittlung von Mathematik in der Schule sowie die Situation an den Unis (Stichwort Halbtagsstelle). Mag sein, dass auch diese Folge am renomierten Karlsruher Institut für Mathematik entstanden ist, aber mit Wissenschaft hat das fast nichts mehr zu tun. Es ist vielmehr ein Beispiel dafür, was alles falsch läuft in der Wissenschaft.

Das Hauptproblem scheint mir zu sein, dass sich die Vortragenden in der Verantwortung als Wissenschaftler sehen anstatt sich als Programmierer / Hacker oder Anti-Scientists zu verstehen. Einmal mehr zeigt sich, dass die Strikte Trennung zwischen theoretischer Informatik und Mathematik keine gute Entscheidung war.

Die Trennung zwischen Mathematik und Informatik

Auf Online-Portalen wie online-vorlesungen.de wird zwischen zwei Vorlesungen unterschieden. Einmal gibt es die Mathematik und einmal die Informatik. Wo genau ist der Unterschied? Grob kann man sagen, dass alle Vorlesungen aus dem Bereich der Mathematik eine veraltete Mathematik diskutieren. Genauer gesagt eine Wissenschaft die bis ungefähr 1920 relevant war. Thema derartiger Vorlesungen können sein: Differentialgleichungen, lineare Optimierung, Gruppentheorie, Algebra. Gemeinsames Merkmal dieser Vorlesung ist, dass sie ihren Schwerpunkt in der Didaktik haben, es wird typischer Klippschulunterricht geboten bei dem es nicht um die Mathematik als solche geht sondern um die Frage wie man Mathematik anderen vermittelt. In den Informatik-Vorlesungen geht es deutlich wissenschaftlicher zu. Dort ist besonders die Kategorie „Theoretische Informatik“ von Interesse. Unter dieser Überschrift werden Entwicklungen behandelt die in der Mathematik ab ungefähr dem Jahr 1920 einsetzten. Ausgehend von dem Gödel Unvollständigkeitssatz wird die Automatentheorie behandelt. Man kann sagen, dass die theoretische Informatik die eigentliche wissenschaftliche Mathematik beinhaltet und für die Gegenwart und besonders für die Zukunft eine hohe Bedeutung besitzt.

Mathematik und Informatik lässt sich gut auseinanderhalten. Die Mathematik beschäftigt sich mit leichten Problemen, also solchen von denen die Lösung bekannt ist. Damit ist beispielsweise ein Gleichungssystem gemeint wo drei Gleichungen und drei Unbekannte existieren. Innerhalb der Mathematik wird jetzt dafür eine Lösung gefunden. Oder ein anderes Beispiel ist die Frage welche Steigung eine Kurve in einem Punkt hat. Derartige Fragen kann man entweder manuell lösen, oder Computersoftware wie Mathematica verwenden. Dadurch wird die Mathematik zu einer sehr überschaubaren Angelegenheit wo es keinerlei Überraschungen mehr gibt. Die wirklich kniffligen Probleme für die keine Lösungen bekannt sind, werden hingegen von der theoretsichen Informatik und darauf aufbauenden Fächern angegangen. Die Informatik unterscheidet zwischen Problemen deren Lösung bekannt ist und Probleme für die es keine Lösung gibt. Die Informatik ist in der Lage sämtliche Probleme der Mathematik zu lösen. Sie hat dafür neben Mathematica noch viele weitere Computerprogramme entwickelt. Gemeinsames Merkmal ist, dass der Algorithmus bekannt ist und das die Ausführung auf einem Standard-PC in unter 1 Minute möglich ist. Was jedoch ungleich spannender in der Informatik und damit auch für die Mathematik sind, das sind Probleme die als np-hart bezeichnet werden. Also Probleme für die kein Algorithmus bekannt ist und dessen Lösung auf einem Standard-PC sehr lange dauern würde. Diese np-harten Probleme sind die eigentliche Mathematik der Gegenwart, wo es also Herausforderungen gibt, die noch keiner vorher bewältigt hat. Hier besteht Forschungsbedarf.

Der Hauptfehler den die meisten Mathematiker machen ist, dass ihnen selbst nicht klar ist, dass ihr Fach keine Bedeutung besitzt. Damit ist gemeint, ihnen ist nicht klar, dass sämtliche Probleme innerhalb der Mathematik bis 1920 gelöst sind, dass es keine echten Herausforderungen mehr gibt. Stattdessen glauben viele Mathematiker, dass eine Aufgabe schwer ist, wenn sie viele Klammern enthält oder wenn komplexe Zahlen darin enthalten sind. Erschwerend kommt hinzu, dass die meisten Mathematiker nicht über die Entwicklungen unterricht sind, die ab den 1920’er Jahren im Rahmen der Turing-Machine stattgefunden haben. Sie haben entweder noch etwas von np-harten Problemen gehört, oder sie glauben, dass es nichts mit Mathematik zu tun hätte. Im wesentlichen zeichnet sich die Hochschulmathematik dadurch aus, dass sie die Wirklichkeit leugnet. Die Gefängnismauern innerhalb derer die Mathematik bewegt sind selbst verursacht. Denn man kann in jeder Leihbücherei nachlesen, was Alan Turing, Kurt Gödel und all die anderen Mathematiker erforscht haben und wiso das die Mathematik auf eine gänzlich neue Stufe gebracht hat. Komisshcrweise findet diese Auseinandersetzung nicht statt. Innerhalb einer Mathematik-Vorlesung wird man niemals den Begriff „Automatentheorie“ hören, obwohl sich darüber die Mathematik sehr viel leichter verstehen lässt.

Wie kann man darauf auf Neueinsteiger reagieren? Nehmen wir mal an, jemand interessiert sich für Mathematik und für Informatik. Dann lautet mein Tipp, die Mathematik komplett zu ignorieren und sich stattdessen mit theoretischer Informatik zu beschäftigen. Unter diesem Stichwort findet man die richtigen Bücher, die richtigen Professoren und die richtigen Lehrveranstaltungen. Theoretische Informatik ist die bessere Mathematik, man kann es auch als moderne Mathematik bezeichnen. Auch Stephen Wolfrom mit seinem Buch „A new kind of science“ ist in diesen Bereich einzuordnen. Es handelt sich um eine Einführung in theoretische Informatik. Um vielleicht einmal auf die Eingangs erwähnte URL zurückzukommen. http://www.online-vorlesungen.de/Videos/Informatik/Theoretische_Informatik.htm Unter dieser Adresse findet man viele Online-Vorlesungen die wirkliche Wissenschaft sind. Ein erster Überblick hat ergeben, dass sie durchweg empfehlenswert sind. Es gibt zwar auch dort Dozenten die nur oberflächliche Informationen bieten und Videos die schon etwas älter sind, aber das sind Detailprobleme in einem grundsätzlich positiven Umfeld. Bei den Mathematik-Vorlesungen auf dem selben Portal ist es genau andersherum …

Die Frage die sich anschließt lautet: wie bringt man das wunderbare Fach „theoretische Informatik“ in die Grundschulen? Weil das etwas wäre, was den Nachwuchs wirklich weiterbringt.

Mathematik als Königin der Wissenschaft?

Überlicherweise wird Mathematik als Vorzeige Wissenschaft präsentiert, als Krone des menschlichen Geistes von der alle anderen Wissenschaften zehren. Wenn Kritik an der Mathematik geübt wird, dann eher von denen die sie nicht verstehen, also von Studenten die eine Klausur bestehen müssen aber keinen Plan haben von gar nichts. Dort gilt Mathematik als zu abstrakt und zu rational. Es gibt jedoch noch eine dritte Möglichkeit über Mathematik zu philosophieren, und das soll im folgenden erläutert werden.

Das merkwürdige am Fach Mathematik ist die Tatsache, dass es offenbar keine Fachkonferenzen gibt, also wo sich Profimathematiker austauschen und über die neusten Entwicklungen in ihrem Fach debattieren. Was es jedoch gibt, sind Didaktik-Konferenzen wo also von Wissenschaftlern darüber diskutiert wird, wie man Mathematik am besten unterrichtet und ob der Taschenrechner etwas in der Grundschule zu suchen hat oder nicht. Bei allen anderen Fächern in der Wissenschaft wie Physik oder Biologie ist es üblich, dass es Konferenzen über das Fach als solches gibt. Im Beispiel der Mathematik würde es bedeuten, dass man sich über Differentialgleichungen unterhält und darüber wie da der aktuelle Stand ist. Der Grund warum sowas nicht durchgeführt hat damit zu tun, dass es keine Neuigkeiten gibt. Warum das so ist kann man mit einem Blick in die Geschichte der Mathematik ermitteln.

Ab ungefähr dem Jahr 1930 wurde innerhalb der Mathematik die Turing-Machine erfunden. Es handelt sich um ein formales Modell um Dinge zu berechnen. Mit einer Turing-Maschine kann man die komplette Mathematik emulieren. Und seit diesem Zeitpunkt geht es nicht mehr um die Mathematik früherer Zeiten sondern was stattdessen im Mittelpunkt steht sind Programme für die Turing-Maschine. Das heißt, es wird darüber gestritten wie man einen Computer programmiert. Dies wird üblicherweise als Informatik bzw. als Softwareengineering bezeichnet. Und das ist die eigentliche State-of-the-art Mathematik.

Dazu vielleicht ein Beispiel: relativ früh hat man angefangen, sogenannte Computeralgebra System zu entwickeln. Das sind Programme wie Mathlab, Mathematica, Mupad usw. mit denen sich Funktionen plotten lassen und Gleichungen umstellen. Die Schwierigkeit ist weniger mit diesen Programmen Mathematik zu betreiben, also eine Aufgabe auszurechnen sondern die Herausforderung besteht darin, derartige Programme in C++ zu schreiben. Darüber unterhält sich die Mathematik-Elite auf den Konferenzen. Komischerweise wird sowas jedoch nicht im Mathematikuntericht an den Schulen oder Universitäten unterrichtet. Wir haben also den seltenen Fall, dass es eine unterrichtete Mathematik gibt, die besteht aus Bruchrechnen, Binomischen Formeln und Differentialgleichungen. Diese unterrichtete Mathematik ist jedoch für echte Mathematiker komplett langweilig. Weil, die benutzen ohnehin Softwareprogramme und viele können gar keine Formeln umstellen.

Welchen Zweck hat also die Schulmathematik? Die Antwort ist ernüchternd: es gibt keinen. Sondern Mathematik hat die Funktion von Latein eingenommen und soll ein bestimmtes gesellschaftliches Bild erzeugen. Nichts, aber wirklich gar nichts was im Mathematik-Unterricht vorkommt hat für später eine Relevanz. Ganz besonders nicht, wenn man sich auf wissenschaftlichem Niveau damit auseinandersetzt.

Böse formuliert ist der Mathematik-Unterricht eine Art von Bestrafungsinstrument, dient der Einschüchterung, soll Lebenschancen verbauen und soll Respekt lehren. Kommen wir zur Eingangsthese zurück, dass Mathematik die Königin der Wissenschaft wäre. Früher hatte sie einmal diese Rolle, aber heute nicht mehr. Stattdessen darf man Informatik als Königin der Wissenschaft bezeichnen. Informatik hat auch etwas mit Mathematik zu tun, aber es behandelt noch viel mehr Themen. Informatik ist eine Art von Klammer, innerhalb derer man jede andere Wissenschaft betreiben kann. Ich würde sogar soweit gehen und zu fordern, Mathematik aus dem Lehrplan von Universitäten zu streichen. Das Fach ist entbehrlich, die Inhalte können in den anderen Fächern mit unterrichtet werden. Das heißt, wenn Biologen unbedingt ausrechnen müssen, wie die Wachstumsrate einer Hasenpopulation ist, kann man das mit einem Excel Chart nebenbei machen ohne das seperat überprüft wird, ob man jetzt richtig gerechnet hat.

Wollte man wirklich etwas unterrichten wie Kerninformatik, so müsste man dort den Ansatz wählen den Stephen Wolfram in seinem Buch „A new kind of science“ vorgestellt hat. Das heißt, man erläutert was ein zellulärer Automat ist und wiso die Rule 110 turing-mächtig ist. Das wäre richtige Mathematik, die so auch für Fachleute von Interesse ist. Darauf aufbauend könnte man dann über Künstliche Intelligenz, sich-selbst reproduzierende Systeme und über Feedback-Loops philosophieren. Mir ist jedoch keine Universität oder Schule bekannt, wo sowas bereits behandelt wird.

Häufig wird behauptet, dass es innerhalb der Mathematik Methoden und Modelle gäbe die sehr mächtig wären und die man in anderen Wissenschaften einsetzen könnte. Beispielsweise um Zufallsprozesse zu beschreiben, um Simulationen durchzuführen oder um Beziehungen abstrakt zu beschreiben. Doch damit überschätzt man die Mathematik. Im Grunde hat sie nichts weiter zu bieten als die Zahlen, Brüche und einige Klammern. Auch Hochtrabende Symbole wie das Summenzeichen, grichische kleine Buchstaben die besonders in der Stochastik beliebt sind oder das Integralzeichen sind weit weniger mächtig als unterstellt wird. Wer wirklich mächtige Werkzeuge benötigt, die sich von anderen Wissenschaften wie der Linguistik, der Physik, der Sportwissenschaft oder den Literaturwissenschaften einsetzen lässt der sollte seinen Fokus auf die Informatik werfen. Dort heißen diese Werkzeuge Software, Online-Portale und Datenbanken. Das ist der eigentliche Zauberkasten, der das tägliche Leben erleichtert.

Mathematik-Unterricht für Dummies

Mathematik gilt nach wie vor als Horrorfach. Die Antwort die das Bildungssystem typischerweise darauf hat, ist das Niveau abzusenken. Also nur eine einfache Mathematik zu unterrichten und sich für das Erklären besonders viel Zeit zu nehmen. Ironischerweise ist der Königsweg zu guter Mathematik-Didaktik jedoch ein anderer. Wenn ein Student etwas nicht versteht, muss man versuchen die Situation zu eskalieren. Also mit Hardcore-Methoden es erklären. Machen wir es mal ein einem konkreten Beispiel:

An der Tafel steht eine Formel die nach einer Variablen aufgelöst werden soll. Keiner in der Klasse hat einen Plan. Jetzt ist es Aufgabe des Dozenten die großen Geschütze auszupacken und zwar sympy. Das ist ein Plugin für Python was für simples Formelumstellen ein overengineering bedeutet, so als wenn man mit einer Bazuka einen Hasen abknallt. Aber hey, warum nicht? Also tippt man die Formel in sympy ein, und kann das Problem lösen.

Komischerweise wird das in einem typischen Mathematik-Unterricht nicht thematisiert. Der Grund ist, dass Mathematik üblicherweise so funktioniert, dass man die Studenten selber den Algorithmus ausführen lässt. Vielleicht ein weiteres Beispiel: Angenommen es soll die Aufgabe gelöst werden „100 : 7“. Um das zu tun, muss man eine Heuristik anwenden, also eine Abfolge von Schritten bei dem man zuerst 10 : 7 teilt, dann den Rest bestimmt, dann noch etwas untereinander schreibt usw. Normalerweise besteht der Mathematik-Unterricht darin, den Studenten diese Heuristiken zu erklären. Das heißt, die Studenten spielen Computer, sie führen Schritte aus, und am Ende gibt es ein Ereignis. Nur, welchen Nutzen soll das haben? Python kann diese Heuristik ebenfalls ausführen, man braucht dort nur auf solve klicken und hat ebenfalls die Lösung.

Das Problem in der Mathematik-Didaktik besteht darin, dass man ein gestörters Verhältnis zu Algorithmen entwickelt hat. Die Idee lautet, dass man Algorithmen unterrichtet, so dass sie von Menschen ausgeführt werden. Aber die Algorithmen als solche und wie man sie auf einem Computer implementiert werden nicht thematisiert. Man glaubt, das wäre nicht bedeutsam. Echte Mathematik geht anders. Die Einsteiger, die noch gar keinen Plan haben, starten einfach Python und tippen dort die Gleichung ein, während die Profis die etwas anspruchsvollere Herausforderungen suchen, sich überlegen können wie man selber solche Heuristiken in Python formuliert. Also wie ein Computerprogramm aussieht, was eine Gleichung umstellt.

Die Realität an den Hochschulen ist eine andere: üblicherweise sind Taschenrechner und Python-Interpreter ein Tabu. Ihre Benutzung wird nicht erläutert, in einer Matheklausur werden sie als Betrugsversuch bezeichnet. Der Clou ist jedoch, dass durch ein Plugin wie sympy die Mathematik sehr viel leichter wird. Das heißt, gerade Leute die nicht wissen wie man Formeln umstellt werden es zu schätzen wissen.

Guter Mathematik-Unterricht besteht zunächst einmal darin, den Studenten den Taschenrechner zu erklären. Also wo sie drücken müssen, um eine Lösung zu finden. Wenn das klar ist, kann man den Studenten Computeralgebra-Systeme erläutern und ihnen zeigen wie sie Funktionen plotten und das in Lyx einbetten. Und wenn das klar ist, sollte man überleiten zur Automatentheorie, also zu zellulären Automaten, um aufzuzeigen wo der Dozent noch Probleme hat und wo er selber Hilfe benötigt. Denn, man bildet den Nachwuchs ja dafür aus, dass er einmal schlauer wird als man selber.

Warum wird das nicht gemacht? Würde man anfangen, Taschenrechner und erst Recht Python im Mathematik-Unterricht zuzulassen würde vom traditioellen Unterricht nicht mehr viel übrig bleiben. Der komplette Lehrplan wäre hinfällig. Es gäbe vor allem nicht länger die Möglichkeit zwischen schlauen Schülern und dummen Schülern zu unterteilen. Das heißt, man kann nicht länger Schüler vor der Klasse lächerlich machen und ihnen eine 4 auf dem Zeugnis geben.