Chen Lijie, ein Genius aus der Yao Class der Tsinghua-Universität, arbeitet gemeinsam mit Nachwuchstalenten aus der Generation der 2000er zusammen, um durch umgekehrte Denkweise ein 50 Jahre altes Computerproblem zu lösen und es umzustürzen.
Ein Genie aus Tsinghuas Yao-Class hat erneut die Welt der theoretischen Informatik in Aufruhr versetzt!
Seit 50 Jahren versuchen Spitzenwissenschaftler, komplexe Probleme der Informatik wie das "Reisende - Verkäufer - Problem" zu lösen, aber es gibt bisher kaum Fortschritte.
Warum kann man diese Probleme nicht beweisen?
Tatsächlich verbirgt sich die Antwort im Bereich der "Metamathematik".
Genau im vergangenen Jahr erschien still und leise eine Dissertation mit dem Titel "Reverse Mathematics Below the Turing Jump".
Die Autoren sind nur drei Personen: Chen Lijie aus Tsinghuas Yao-Class, der Student Li Jiatu sowie der bekannte Informatikwissenschaftler Igor Carboni Oliveira.
Link zur Dissertation: https://eccc.weizmann.ac.il/report/2024/060/
Anstatt sich an den traditionellen Weg zu halten, Theoreme aus Axiomen abzuleiten, wählten sie einen anderen Weg und verwendeten die Methode der "Reverse Mathematics" aus der "Metamathematik".
Überraschenderweise stellten sie fest, dass viele Theorien, die auf den ersten Blick völlig unabhängig voneinander scheinen, in der untersten logischen Ebene völlig äquivalent sind.
Zum Beispiel das "Schubfachprinzip" und die "Palindrom - untere Schranke" einer Turing - Maschine.
Mit der Veröffentlichung dieser Dissertation wurde die "Weltanschauung" der Menschen völlig umgeworfen.
In den letzten fünfzig Jahren verfolgten Informatikwissenschaftler den Gedanken, "stärkere Axiome beweisen schwierigere Theoreme", doch es stellte sich heraus, dass dieser Ansatz von Anfang an falsch war.
Die Mathematik "umkehren"
Das Jahrtausende alte Denkparadigma umwerfen
Wenn man an diese schwierigen Probleme denkt, scheinen Informatikwissenschaftler auf dem Schlauch zu stehen.
Nehmen wir das berühmte "Reisende - Verkäufer - Problem" als Beispiel. Auf den ersten Blick ist es nur ein kombinatorisches Optimierungsproblem:
Man muss auf einer Karte die kürzeste Route finden, die jede Stadt genau einmal besucht und am Ende wieder zum Ausgangspunkt zurückkehrt.
Aber sobald die Anzahl der Städte etwas größer wird, beginnen die Wissenschaftler zu zweifeln, dass es eine gute Lösung gibt. Das Problem ist, dass niemand weiß, wie man dies beweisen kann.
In den letzten 50 Jahren haben die Experten in der Theorie der Berechnungskomplexität versucht, diese "Intuition" in feste mathematische Theoreme umzuwandeln.
Tatsächlich scheiterten sie wieder und wieder und fanden keinen Durchbruch.
Deshalb begannen sie immer mehr darüber nachzudenken, warum die Beweise immer fehlschlagen.
Die "Metamathematik" nimmt die Beweise selbst als Forschungsgegenstand.
Wenn Forscher die Theorie der Komplexität mit der "Metamathematik" untersuchen, versuchen sie herauszufinden -
Welche Schlussfolgerungen über die Berechnungsschwierigkeit man mit verschiedenen Axiomensätzen beweisen oder nicht beweisen kann.
Warum man beim Beweis, dass ein Problem "schwierig" ist, immer einen Schritt fehlt.
Im April 2024 unternahmen die drei Autoren in ihrer Dissertation etwas, das die Vorgänger nicht einmal wagen wollten: Sie kehrten das Jahrtausende alte Denkparadigma der Mathematik völlig um.
Der traditionelle Weg ist, dass man ausgehend von einem Satz von Axiomen eine Reihe von Theoremen ableitet.
Jetzt taten sie das Gegenteil - sie ersetzten ein Axiom durch ein Theorem und versuchten, das ersetzte Axiom zu beweisen.
Wie der Titel der Dissertation zeigt, wird dieser Prozess "Reverse Mathematics" genannt.
Es wurde bewiesen, dass eine Vielzahl von "Komplexitäts - Theoremen", die auf den ersten Blick völlig unabhängig voneinander scheinen, in der Logik völlig äquivalent sind.
Marco Carmosino, ein Komplexitätstheoretiker von IBM, reagierte auf die Dissertation mit: "Ich war schockiert, dass sie so viel erreichen konnten."
Jeder, der die Dissertation liest, wird sagen: "Diese Dissertation hat mich in die Welt der 'Metamathematik' gezogen!"
Beweise mit Tauben, abwegig
Die Geschichte beginnt im Sommer 2022.
Damals stand Chen Lijie kurz vor seinem Doktorgrad an der MIT. Da er plötzlich viel Freizeit hatte, beschloss er, ein paar Monate in die Metamathematik einzusteigen.
Er sagte: "Da ich bald promovierte und keine großen Forschungsaufgaben mehr hatte, dachte ich, ich sollte etwas Neues lernen."
Während des Studiums begann Chen Lijie, über einen Zweig der Komplexitätstheorie nachzudenken: die Kommunikationskomplexität.
Dieser Bereich beschäftigt sich hauptsächlich damit, wie viel Information zwei oder mehrere Personen austauschen müssen, um eine Aufgabe zu erfüllen.
In der Kommunikationskomplexität gibt es ein einfaches Problem namens "Gleichheitsproblem", das wie ein Kooperationsspiel aussieht:
Zwei Spieler halten jeweils eine Zeichenkette aus 0 und 1 in der Hand. Ihr Ziel ist es, mit möglichst wenig Kommunikation herauszufinden, ob die Zeichenketten identisch sind.
Die dümmlichste Methode wäre, dass ein Spieler seine gesamte Zeichenkette an den anderen schickt, damit dieser prüfen kann.
Außerdem haben Komplexitätstheoretiker vor einigen Jahrzehnten bewiesen, dass es keine bessere Möglichkeit gibt.
Um das "Gleichheitsproblem" zu lösen, muss man mindestens so viele Bits senden, wie die Länge der Zeichenkette beträgt. Die Theoretiker nennen diese Länge die "untere Schranke" des erforderlichen Kommunikationsaufwands.
Chen Lijie interessierte sich nicht für die "untere Schranke" selbst, sondern für die Art und Weise, wie die Forscher sie bewiesen haben.
Alle bekannten Beweise beruhen auf einem einfachen Theorem - dem Schubfachprinzip (auch "Schubfachlemma" genannt).
Dieses Prinzip besagt: Wenn man eine Anzahl von Tauben in weniger Löchern als Tauben unterbringt, muss mindestens ein Loch mehr als eine Taube enthalten.
Dies klingt wie Selbstverständlichkeit, aber in der Komplexitätstheorie und vielen anderen Bereichen ist es ein sehr mächtiges Werkzeug.
Also bemerkte Chen Lijie einen wichtigen Hinweis -
Die Verbindung zwischen dem "Gleichheitsproblem" und dem "Schubfachprinzip" könnte zweierlei sein.
Es ist einfach, die untere Schranke des Gleichheitsproblems mit dem Schubfachprinzip zu beweisen. Aber kann man umgekehrt das Schubfachprinzip mit der unteren Schranke beweisen?
Die seltsame Äquivalenz
Also nahm Chen Lijie den Tsinghua - Studenten Li Jiatu, mit dem er gerade eine Dissertation zusammen geschrieben hatte, mit und begann eine neue Erkundung.
Um diese Verbindung mathematisch zu begründen, mussten sie ein Satz von Axiomen als "Grundlage" auswählen.
Sie wählten ein beliebtes Axiomensystem namens PV₁ und begannen mit der "Umkehrung".
Da PV₁ stark genug ist, um einige wichtige Theoreme in der Berechnungskomplexität unabhängig zu beweisen, kann man, wenn man auf der Grundlage von PV₁ ein spezielles "Schubfachprinzip" als zusätzliches Axiom hinzufügt, die untere Schranke des "Gleichheitsproblems" beweisen.
Im Dezember 2022 hatten sie Erfolg!
Das Ergebnis bestätigte genau die ursprüngliche Vermutung von Chen Lijie: Wenn man die Positionen der Theoreme vertauscht, ist der Beweis immer noch gültig.
Im logischen Rahmen von PV₁ sind die beiden Theoreme völlig äquivalent.
Als sie das Ergebnis mit Igor Oliveira, einem Komplexitätstheoretiker von der Universität Warwick, diskutierten, erkannten sie plötzlich -
Die Methode der "Reverse Mathematics" könnte auch auf andere scheinbar unabhängige Bereiche der Komplexitätstheorie angewendet werden.
In den folgenden Monaten bewiesen sie systematisch, dass viele andere Theoreme ebenfalls äquivalent sind.
Chen Lijie sagte: "Anfangs wollten wir nur zwei Theoreme als äquivalent beweisen, aber jetzt haben wir ein großes Netzwerk von Äquivalenzen."
Die erstaunlichste Verbindung, die das Team entdeckte, war die Verbindung zwischen einer Version des "Schubfachprinzips" und einem der ersten Theoreme, die Studenten in der Einführungskurs in die Komplexitätstheorie lernen.
Dieses klassische Theorem legt die untere Schranke der Zeit fest, die eine einfache Band - Turing - Maschine benötigt, um zu entscheiden, ob eine Zeichenkette aus 0 und 1 ein Palindrom ist (vorwärts und rückwärts gelesen gleich).
Die "Reverse Mathematics" bewies, dass im Rahmen von PV₁ dieses "Palindrom - untere Schranke" - Theorem und das Schubfachprinzip äquivalent sind.
Selbst Chen Lijie sagte ungläubig: "Wenn mir jemand diesen Satz direkt erzählen würde, würde ich es nicht glauben. Es klingt zu abwegig."
Dieser Satz ist so überraschend, weil die beiden Theoreme auf den ersten Blick völlig verschieden sind.
Das "Schubfachprinzip" hat im Wesentlichen nichts mit der Berechnung zu tun, sondern ist ein einfaches Prinzip der Zählung.
Die Palindrom - untere Schranke dagegen ist eine Aussage über ein spezielles Berechnungsmodell.
Dieses neue Ergebnis bedeutet, dass diese scheinbar sehr speziellen Theoreme viel allgemeiner und grundlegender sind, als sie auf den ersten Blick erscheinen.
Oliveira sagte: "Dies zeigt, dass die Komplexitäts - unteren Schranken, die wir verstehen möchten, viel grundlegender sind."
Unbekanntes Territorium, solide Grundlagen benötigt
Glücklicherweise hat dieses neue "Netzwerk von Äquivalenzen" den Wissenschaftlern auch die Grenzen von PV₁ klar gemacht.
Es war bereits bekannt, dass man das "Schubfachprinzip" allein mit den Axiomen von PV₁ nicht beweisen kann.
Das bedeutet also, dass die anderen äquivalenten Theoreme im Netzwerk wahrscheinlich auch in PV₁ nicht zu beweisen sind.
Ján Pich, ein Komplexitätstheoretiker von der Universität Oxford, sagte: "Ich finde es wunderschön."
Aber er warnte gleichzeitig: "Die Methode der 'Reverse Mathematics' eignet sich am besten, um neue Verbindungen zwischen bereits bewiesenen Theoremen aufzudecken."
"Für Aussagen, die wir noch nicht beweisen können, kann es uns derzeit nicht viel über ihre Komplexität sagen."
Das Verständnis dieses unbekannten Territoriums ist für Forscher in der "Metamathematik" noch ein fernes Ziel.
Aber das hat die Begeisterung von Li Jiatu für dieses Fach nicht gedämpft.
Im Jahr 2023 begann er sein Studium als Graduiertstudent an der MIT. Kürzlich schrieb er sogar eine 140 - Seiten - lange Anleitung zur Metamathematik für Komplexitätstheoretiker.
