Ein in diesem Monat online gestelltes Papier hat eine fast 30 Jahre alte Vermutung über die Struktur der Grundbausteine von Computerschaltungen aufgestellt. Diese "Sensitivitäts" -Vermutung hat im Laufe der Jahre viele der bekanntesten Informatiker überrumpelt, doch der neue Beweis ist so einfach, dass ein Forscher ihn in einem einzigen Tweet zusammengefasst hat.
"Diese Vermutung hat sich als eines der frustrierendsten und peinlichsten offenen Probleme in der gesamten Kombinatorik und theoretischen Informatik erwiesen", schrieb Scott Aaronson von der University of Texas, Austin, in einem Blogbeitrag. "Die Liste der Leute, die versuchten, es zu lösen und scheiterten, ist wie ein Who is Who der diskreten Mathematik und der theoretischen Informatik", fügte er in einer E-Mail hinzu.
Die Vermutung betrifft Boolesche Funktionen, Regeln zum Transformieren einer Folge von Eingabebits (0s und 1s) in ein einzelnes Ausgabebit. Eine solche Regel besteht darin, eine 1 auszugeben, vorausgesetzt, eines der Eingangsbits ist 1 und andernfalls eine 0; Eine andere Regel ist, eine 0 auszugeben, wenn der String eine gerade Zahl von 1s hat, und eine 1, wenn dies nicht der Fall ist. Jeder Computerkreis ist eine Kombination von Booleschen Funktionen, die sie zu "Bausteinen für alles machen, was Sie in der Informatik tun", sagte Rocco Servedio von der Columbia University.
Im Laufe der Jahre haben Informatiker viele Methoden entwickelt, um die Komplexität einer bestimmten Booleschen Funktion zu messen. Jede Kennzahl erfasst einen anderen Aspekt davon, wie die Informationen in der Eingabezeichenfolge das Ausgabebit bestimmen. Zum Beispiel wird durch die „Empfindlichkeit“einer Booleschen Funktion grob gesagt die Wahrscheinlichkeit verfolgt, dass das Spiegeln eines einzelnen Eingabebits das Ausgabebit ändert. Und „Abfragekomplexität“berechnet, nach wie vielen Eingabebits Sie fragen müssen, bevor Sie sich der Ausgabe sicher sein können.
Jede Kennzahl bietet ein eindeutiges Fenster in die Struktur der Booleschen Funktion. Dennoch haben Informatiker festgestellt, dass fast alle diese Maßnahmen in einen einheitlichen Rahmen passen, so dass der Wert eines von ihnen ein grobes Maß für den Wert der anderen ist. Nur ein Komplexitätsmaß schien nicht zu passen: Sensibilität.
Im Jahr 1992 vermuteten Noam Nisan von der Hebrew University in Jerusalem und Mario Szegedy von der Rutgers University, dass Sensibilität tatsächlich in diesen Rahmen passt. Aber niemand konnte es beweisen. "Dies war wahrscheinlich die offene Frage beim Studium der Booleschen Funktionen", sagte Servedio.
"Die Leute schrieben lange, komplizierte Papiere, um den geringsten Fortschritt zu erzielen", sagte Ryan O'Donnell von der Carnegie Mellon University.
Jetzt hat Hao Huang, Mathematiker an der Emory University, die Sensitivitätsvermutung mit einem genialen, aber elementaren zweiseitigen Argument über die Kombinatorik von Punkten auf Würfeln bewiesen. "Es ist einfach wunderschön wie eine kostbare Perle", schrieb Claire Mathieu vom französischen Nationalen Zentrum für wissenschaftliche Forschung während eines Skype-Interviews.
Aaronson und O'Donnell nannten beide Huangs Papier den „Buchbeweis“für die Sensitivitätsvermutung und bezogen sich dabei auf Paul Erdős Vorstellung von einem Himmelsbuch, in dem Gott den perfekten Beweis für jeden Satz schreibt. „Es fällt mir schwer, mir vorzustellen, dass selbst Gott die Sensitivitäts-Vermutung auf einfachere Weise beweisen kann“, schrieb Aaronson.
Eine sensible Angelegenheit
Stellen Sie sich vor, Mathieu sagte, dass Sie eine Reihe von Ja / Nein-Fragen zu einem Bankkreditantrag ausfüllen. Wenn Sie fertig sind, bewertet der Bankier Ihre Ergebnisse und teilt Ihnen mit, ob Sie sich für einen Kredit qualifizieren. Dieser Prozess ist eine Boolesche Funktion: Ihre Antworten sind die Eingabebits und die Entscheidung des Bankers ist das Ausgabebit.
Wenn Ihre Bewerbung abgelehnt wird, fragen Sie sich möglicherweise, ob Sie das Ergebnis durch eine einzige Frage hätten ändern können - vielleicht, indem Sie behaupteten, dass Sie mehr als 50.000 US-Dollar verdienen, wenn Sie dies wirklich nicht tun. Wenn diese Lüge das Ergebnis umgedreht hätte, sagen Informatiker, dass die Boolesche Funktion für den Wert dieses bestimmten Bits "empfindlich" ist. Wenn es beispielsweise sieben verschiedene Lügen gibt, von denen Sie hätten sagen können, dass jede das Ergebnis separat umgedreht hätte, dann ist für Ihr Darlehensprofil die Empfindlichkeit der Booleschen Funktion sieben.
Informatiker definieren die Gesamtsensitivität der Booleschen Funktion als den größten Sensitivitätswert, wenn sie alle möglichen Kreditprofile betrachten. In gewissem Sinne berechnet dieses Maß, wie viele der Fragen in den meisten Grenzfällen wirklich wichtig sind -
die Anwendungen, die am einfachsten in die andere Richtung hätten schwingen können, wenn sie sich so leicht verändert hätten.
Die Empfindlichkeit ist normalerweise eine der am einfachsten zu berechnenden Komplexitätsmaße, aber sie ist bei weitem nicht die einzige aufschlussreiche Maßnahme. Anstatt Ihnen beispielsweise einen Papierantrag zu überreichen, hätte der Bankier Sie befragen können, wobei er mit einer einzelnen Frage begonnen und dann anhand Ihrer Antwort ermittelt hat, welche Frage als Nächstes gestellt werden soll. Die größte Anzahl von Fragen, die der Bankier jemals stellen müsste, um eine Entscheidung zu treffen, ist die Komplexität der Abfrage der Booleschen Funktion.
Diese Maßnahme tritt in einer Vielzahl von Situationen auf - zum Beispiel möchte ein Arzt möglicherweise einen Patienten zu möglichst wenigen Tests schicken, bevor eine Diagnose vorliegt, oder ein Experte für maschinelles Lernen möchte, dass ein Algorithmus so wenige Merkmale eines Objekts wie möglich untersucht bevor Sie es klassifizieren. "In vielen Situationen - Diagnose- oder Lernsituationen - sind Sie wirklich glücklich, wenn die zugrunde liegende Regel… eine geringe Komplexität der Abfrage aufweist", sagte O'Donnell.
Andere Maßnahmen umfassen die Suche nach dem einfachsten Weg, die Boolesche Funktion als mathematischen Ausdruck zu schreiben, oder die Berechnung der Anzahl der Antworten, die der Bankier einem Chef zeigen müsste, um zu beweisen, dass er die richtige Kreditentscheidung getroffen hat. Es gibt sogar eine quantenphysikalische Version der Abfragekomplexität, bei der der Banker mehrere Fragen gleichzeitig überlagern kann. Das Herausfinden, wie dieses Maß mit anderen Komplexitätsmaßen zusammenhängt, hat Forschern geholfen, die Grenzen von Quantenalgorithmen zu verstehen.
Mit Ausnahme der Empfindlichkeit haben Informatiker bewiesen, dass alle diese Maßnahmen eng miteinander verknüpft sind. Insbesondere haben sie eine polynomielle Beziehung zueinander - zum Beispiel könnte ein Maß ungefähr das Quadrat oder der Würfel oder die Quadratwurzel eines anderen sein. Nur die Sensibilität weigerte sich hartnäckig, in diese saubere Charakterisierung zu passen. Viele Forscher vermuteten, dass es tatsächlich dazu gehörte, konnten jedoch nicht beweisen, dass es keine seltsamen Booleschen Funktionen gab, deren Empfindlichkeit eher eine exponentielle als eine polynomielle Beziehung zu den anderen Maßen hatte, was in dieser Situation bedeuten würde, dass das Maß für die Empfindlichkeit immens ist kleiner als die anderen Maßnahmen.
"Diese Frage war den Leuten 30 Jahre lang ein Dorn im Auge", sagte Aaronson.
Die Lösung in die Enge treiben
Huang hörte von der Sensitivitätsvermutung Ende 2012 beim Mittagessen mit dem Mathematiker Michael Saks am Institute for Advanced Study, wo Huang ein Postdoktorand war. Er war sofort von der Einfachheit und Eleganz der Vermutung angetan. "Ab diesem Moment war ich wirklich besessen davon, darüber nachzudenken", sagte er.
Huang fügte die Sensitivitätsvermutung zu einer "geheimen Liste" von Problemen hinzu, an denen er interessiert war, und wann immer er von einem neuen mathematischen Werkzeug erfuhr, überlegte er, ob es helfen könnte. "Jedes Mal, wenn ich eine neue Zeitung veröffentlicht habe, bin ich auf dieses Problem zurückgekommen", sagte er. "Natürlich würde ich nach einer gewissen Zeit aufgeben und an einem realistischeren Problem arbeiten."
Huang wusste ebenso wie die breitere Forschungsgemeinschaft, dass die Sensitivitätsvermutung beigelegt werden konnte, wenn Mathematiker eine leicht zu formulierende Vermutung über Punktsammlungen auf Würfeln unterschiedlicher Dimensionen nachweisen konnten. Es gibt einen natürlichen Weg, von einer Folge von n Nullen und Einsen zu einem Punkt auf einem n-dimensionalen Würfel zu gelangen: Verwenden Sie einfach die n Bits als Koordinaten des Punkts.
Beispielsweise entsprechen die vier Zwei-Bit-Zeichenfolgen - 00, 01, 10 und 11 - den vier Ecken eines Quadrats in der zweidimensionalen Ebene: (0, 0), (0, 1), (1, 0) und (1, 1). Ebenso entsprechen die acht Drei-Bit-Zeichenfolgen den acht Ecken eines dreidimensionalen Würfels usw. in höheren Dimensionen. Man kann sich wiederum eine Boolesche Funktion vorstellen, um diese Ecken mit zwei verschiedenen Farben einzufärben (z. B. Rot für 0 und Blau für 1).
Im Jahr 1992 stellten Craig Gotsman, der jetzt am New Jersey Institute of Technology arbeitet, und Nati Linial von der Hebrew University fest, dass der Nachweis der Sensitivitätsvermutung auf die Beantwortung einer einfachen Frage zu Würfeln unterschiedlicher Dimensionen reduziert werden kann: Wenn Sie eine Sammlung von mehr als auswählen Gibt es immer einen roten Punkt, der mit vielen anderen roten Punkten verbunden ist? (Mit „verbunden“ist hier gemeint, dass sich die beiden Punkte einen der äußeren Ränder des Würfels teilen, anstatt sich über eine Diagonale zu erstrecken.)
Wenn Ihre Sammlung genau die Hälfte der Würfelecken enthält, ist es möglich, dass keine davon verbunden wird. Unter den acht Ecken des dreidimensionalen Würfels befinden sich beispielsweise die vier Punkte (0, 0, 0), (1, 1, 0), (1, 0, 1) und (0, 1, 1) über Diagonalen voneinander. Sobald jedoch mehr als die Hälfte der Punkte in einem Würfel einer beliebigen Dimension rot gefärbt sind, müssen einige Verbindungen zwischen roten Punkten auftauchen. Die Frage ist: Wie sind diese Verbindungen verteilt? Wird es mindestens einen stark vernetzten Punkt geben?
Im Jahr 2013 begann Huang zu überlegen, dass der beste Weg zum Verständnis dieser Frage die Standardmethode sein könnte, ein Netzwerk mit einer Matrix darzustellen, die verfolgt, welche Punkte verbunden sind, und dann eine Menge von Zahlen zu untersuchen, die als Eigenwerte der Matrix bezeichnet werden. Fünf Jahre lang hat er diese Idee ohne Erfolg wiederholt. "Aber zumindest hat es mir geholfen, viele Nächte lang schnell einzuschlafen", kommentierte er Aaronsons Blog-Post.
Dann kam Huang im Jahr 2018 auf den Gedanken, ein 200 Jahre altes Stück Mathematik zu verwenden, das als Cauchy-Interlace-Theorem bezeichnet wird und die Eigenwerte einer Matrix mit denen einer Submatrix in Beziehung setzt, was es möglicherweise zum perfekten Werkzeug macht, um die Beziehung zwischen einem Würfel und zu untersuchen eine Teilmenge seiner Ecken. Huang beschloss, ein Stipendium der National Science Foundation zu beantragen, um diese Idee weiter zu untersuchen.
Als er letzten Monat in einem Madrider Hotel saß und seinen Zuschussantrag schrieb, wurde ihm plötzlich klar, dass er diesen Ansatz ganz zum Tragen bringen konnte, indem er einfach die Vorzeichen einiger Zahlen in seiner Matrix vertauschte. Auf diese Weise konnte er nachweisen, dass es in jeder Sammlung von mehr als der Hälfte der Punkte in einem n-dimensionalen Würfel einen Punkt geben wird, der mindestens mit der Quadratwurzel von n der anderen Punkte verbunden ist. und die Empfindlichkeitsvermutung folgte sofort aus diesem Ergebnis.
Als Huangs Zeitung in Mathieus Posteingang landete, war ihre erste Reaktion „Oh, oh“, sagte sie. „Wenn ein Problem etwa 30 Jahre alt ist und jeder davon gehört hat, ist der Beweis wahrscheinlich entweder sehr lang und mühsam und kompliziert oder er ist sehr tief.“Sie schlug die Zeitung auf und erwartete, nichts zu verstehen.
Aber der Beweis war für Mathieu und viele andere Forscher einfach genug, um in einer Sitzung zu verdauen. "Ich gehe davon aus, dass es in diesem Herbst - in einer einzigen Vorlesung - in jedem Kombinatorikkurs auf Master-Niveau unterrichtet wird", teilte sie über Skype mit.
Huangs Ergebnis ist sogar noch stärker als nötig, um die Sensitivitätsvermutung zu beweisen, und diese Kraft sollte neue Erkenntnisse über Komplexitätsmaße liefern. "Es ergänzt unser Toolkit, um möglicherweise zu versuchen, andere Fragen bei der Analyse von Booleschen Funktionen zu beantworten", sagte Servedio.
