Суперкомпьютеры не справились с решением задачи Рэми о вечеринках

Mathematische Unterhaltungen: Das Partyproblem, an dem Computer scheitern Die Planung einer Party führt zu einer grundlegenden Frage der Mathematik: Ab welcher Größe entsteht selbst im größten Chaos ein regelmäßiges Muster? Die Antwort verbindet Kombinatorik und Logik – und bringt selbst Supercomputer an ihre Grenzen. von Bernd Steinbach und Christian Posthoff Manchmal entsteht ein ganzes Forschungsgebiet aus einer scheinbar harmlosen Frage: Wie viele Menschen muss man zu einer Party einladen, damit sich zwangsläufig eine kleine Gruppe findet, in der entweder alle miteinander bekannt sind – oder niemand den anderen kennt? Dahinter verbirgt sich ein wichtiges Prinzip der Kombinatorik: In hinreichend großen Strukturen ist Ordnung unvermeidbar. Die Grundidee der sogenannten Ramsey-Theorie klingt damit fast philosophisch. Wenn eine Struktur nur groß genug ist, kann sie nicht beliebig chaotisch bleiben. In jedem noch so kunstvoll gefärbten, sortierten oder verschlüsselten Gebilde tauchen irgendwann regelmäßige Teilstrukturen auf. Diese Schwelle entspricht einer Ramsey-Zahl, benannt nach dem britischen Mathematiker und Logiker Frank Plumpton Ramsey, der deren grundlegenden Existenzsätze im Jahr 1930 in der Arbeit » On a Problem of Formal Logic « veröffentlichte. Der Titel deutet darauf hin, dass die Ramsey-Theorie nicht nur reine Kombinatorik ist. Seit ihren Anfängen gibt es auch eine Verbindung zur Logik. Doch auch fast 100 Jahre nach ihrem Aufkommen – und trotz zahlreicher Bemühungen – sind bislang nur sehr wenige Ramsey-Zahlen bekannt. Obwohl die zugrunde liegenden Fragestellungen einfach wirken, wachsen die Probleme schnell zu kosmischer Größe an. Deshalb sind Mathematikerinnen und Mathematiker in diesem Bereich auf die Unterstützung von Computern angewiesen. Selbst diese haben aber ihre Grenzen. Der mächtigste Supercomputer allein nützt nichts, wenn Menschen nicht durch ausgeklügelte Überlegungen die betreffenden Suchräume einschränken. Damit steht die Ramsey-Theorie für einen Ausnahmebereich der modernen Mathematik, in dem Mensch und Maschine gemeinsam voranschreiten. Die perfekte Größe einer Party Das klassische Einführungsbeispiel zur Ramsey-Theorie handelt von einer Party. Angenommen, man möchte sicher sein, dass unter den Gästen entweder drei Personen sind, die sich alle gegenseitig kennen, oder drei Personen, die sich alle fremd sind. Im ersten Fall könnten die drei an gemeinsame Erinnerungen anknüpfen, im zweiten entstünde Raum für neue Bekanntschaften. Wie viele Gäste muss man mindestens einladen, damit eine der beiden Situationen unvermeidlich eintritt? Diese Frage lässt sich als Problem der Graphentheorie formulieren. Die Gäste werden zu den Knoten, also den Punkten. Zwischen je zwei Knoten zieht man eine Kante. Und dann kommen Farben ins Spiel: Je zwei Personen können sich entweder kennen – dann färbt man die Kante rot – oder nicht. In diesem Fall färbt man sie blau. Die ursprüngliche Partyfrage wird damit zur Frage nach farbigen Dreiecken: Gibt es in einem rot-blau gefärbten Graphen K n ​zwangsläufig ein Dreieck, dessen drei Kanten alle rot oder alle blau sind? Ein solches Dreieck entspricht nämlich drei Gästen, die sich alle gegenseitig kennen oder die einander alle fremd sind. Die Ramsey-Zahl R(3,3) ist die kleinste Anzahl an n  Knoten, für die ein solches einfarbiges Dreieck in jeder möglichen Rot-Blau-Färbung von K n ​ auftreten muss (die erste 3 in R(3,3) steht für ein rotes Dreieck, die zweite 3 für ein blaues). R(3,3) lässt sich noch mit überschaubaren Überlegungen berechnen. Zunächst zeigt man, dass fünf Gäste nicht ausreichen. Es gibt nämlich ein Beispiel für einen Graphen  K 5, in dem kein rotes und kein blaues Dreieck vorkommt. Bei fünf Personen kann man die Bekanntschaftsbeziehungen also so anordnen, dass es weder drei gegenseitig bekannte noch drei gegenseitig unbekannte Personen gibt. Deshalb muss R(3,3) größer als 5 sein. Also betrachtet man den nächstgrößeren Graphen K 6. Man versucht, die sechs Knoten so zu färben, dass weiterhin kein einfarbiges Dreieck entsteht. Dieser Versuch scheitert allerdings. Wie sich herausstellt, ist in einem vollständigen Graphen mit sechs Knoten und rot-blau gefärbten Kanten ein einfarbiges Dreieck unvermeidlich. Deshalb folgt R(3,3) = 6. Ramsey-Zahl R(3,3) Einen Graphen mit fünf Knoten kann man so mit zwei Farben färben, dass kein einfarbiges Dreieck entsteht. Deshalb versucht man als Nächstes, die Kanten eines Graphen mit sechs Knoten entsprechend einzufärben. Um das zu bewerkstelligen, kann man sich zunächst einen einzelnen Knoten A herauspicken und untersuchen, wie die Beziehung zu den übrigen Knoten aussehen kann. Es gibt insgesamt sechs verschiedene Möglichkeiten, mit wie vielen der Geladenen eine Person befreundet sein kann und wie viele ihr fremd sein können: Freunde | Fremde | Mindestanzahl Freunde | Mindestanzahl Fremde 5 | 0 | 3 | - 4 | 1 | 3 | - 3 | 2 | 3 | - 2 | 3 | - | 3 1 | 4 | - | 3 0 | 5 | - | 3 Person A ist also immer mit mindestens drei Personen befreundet – oder ihr sind mindestens drei Personen unbekannt. Im Graph macht sich das dadurch bemerkbar, dass von A stets mindestens drei gleichfarbige Kanten ausgehen. Für ein konkretes Beispiel kann man annehmen, ein bestimmter Punkt A habe drei rote Kanten (sprich: Person A kennt drei andere Gäste). Nun kann man versuchen, die restlichen Verbindungen so zu färben, dass ein rotes Dreieck umgangen wird.  Daher muss man sicherstellen, dass jeweils zwei Personen, die A kennt, sich untereinander nicht kennen (also blaue Verbindungen haben). Wenn man all diese Kanten blau markiert, entsteht aber ein blaues Dreieck! Das heißt, es gibt keine Möglichkeit, ein einfarbiges Dreieck in einem Graphen mit sechs Punkten zu umgehen, wenn alle Knoten miteinander verbunden sein müssen. Damit findet man ein solches Dreieck auch in jedem größeren Graphen, bei dem alle Punkte miteinander verbunden sind. Das heißt: Sobald Sie mehr als fünf Gäste einladen, gibt es auf jeden Fall immer ein Dreiergespann, das sich untereinander kennt oder völlig fremd ist. Eine Frage der Logik Graphen sind jedoch nur eine Sprache, mit der man solche Einsichten ausdrücken kann. Es gibt eine zweite, ebenso natürliche Möglichkeit, an Ramsey-Probleme heranzugehen: die Logik. Die Färbung eines Graphen besteht letztlich aus einer langen Liste von Entscheidungen: Ist eine Kante rot oder blau? Damit liegt es nahe, jeder Kante einen von zwei logischen Werten zuzuordnen: eine »boolesche Variable«. Boolesche Variablen können 0 oder 1 sein, in logischer Sprache falsch oder wahr. Sie lassen sich durch die »boolesche Algebra« miteinander verknüpfen. Die Negation einer Variablen x schreibt man als ¬ x, sie kehrt den Wahrheitswert um: Aus wahr wird falsch, aus falsch wird wahr. Neben der Negation gibt es die Verknüpfungen »und« und »oder«, meist geschrieben als ∧ und ∨. Der Ausdruck x ∧ y ist genau dann wahr, wenn sowohl x als auch y wahr sind. Der Ausdruck x ∨ y ist wahr, sobald mindestens eine der beiden Variablen wahr ist. Aus solchen Bausteinen entstehen boolesche Funktionen. Setzt man für alle darin vorkommenden Variablen konkrete Werte ein, ergibt das 0 oder 1, also falsch oder wahr. Werden zwei solche Funktionen gleichgesetzt, erhält man eine boolesche Gleichung. Ihre Lösungen sind jene Variablen, für die beide Seiten denselben Wert ergeben. Dieser Formalismus lässt sich auf Ramsey-Zahlen anwenden. Denn die Kantenfärbung eines Graphen ist nichts anderes als eine Belegung vieler boolescher Variablen. Jede Kante bekommt einen Wert, und damit ist festgelegt, ob sie rot oder blau ist. Die Partyfrage wird dann zur Frage, ob es eine Belegung der Variablen gibt, bei der kein Dreieck einfarbig ist. Betrachten wir zunächst das Dreieck mit den Knoten 1, 2 und 3. Es besitzt drei Kanten: zwischen 1 und 2, zwischen 1 und 3 sowie zwischen 2 und 3. Die zugehörigen Variablen sind k 12, k 13 und k 23. Wenn der Wert 1 für eine rote Kante steht, dann beschreibt der Ausdruck k 12 ∧ k 13 ∧ k 23 den Fall, dass alle drei Kanten des Dreiecks rot sind. Denn dieser Ausdruck wird nur dann wahr, wenn alle drei beteiligten Variablen den Wert 1 besitzen. Analog beschreibt der Ausdruck ¬ k 12 ∧¬ k 13 ∧¬ k 23 den Fall, dass alle drei Kanten blau sind (er wird genau dann wahr, wenn alle drei Variablen 0 sind).  Für ein Ramsey-Problem der Form R(3,3) muss für jedes Dreieck im Graphen gelten: Es darf weder ganz rot noch ganz blau sein. In logischer Sprache: ¬( k 12 ∧ k 13 ∧ k 23 )∧¬(¬ k 12 ∧¬ k 13 ∧¬ k 23 ) Diese Bedingung wiederholt man für jedes Dreieck im Graphen K n, wodurch man ein System boolescher Bedingungen erhält. Ist dieses erfüllbar, dann gibt es eine Rot-Blau-Färbung von  K n ohne einfarbiges Dreieck. Ist es nicht erfüllbar, lässt sich ein einfarbiges Dreieck nicht vermeiden. Für K 5 ist das System erfüllbar. Der vollständige Graph mit fünf Knoten hat zehn Kanten; entsprechend gibt es zehn boolesche Variablen. Außerdem fasst  K 5 zehn Dreiecke, und für jedes davon formuliert man eine logische Bedingung. Löst man das entstehende Gleichungssystem, findet man Färbungen, in denen kein einfarbiges Dreieck vorkommt. Damit ist auch auf diesem Weg gezeigt: Fünf Knoten reichen nicht aus, um ein einfarbiges Dreieck zu erzwingen.  Bei K 6 ändert sich die Lage. Der Graph besitzt 15 Kanten und damit 15 boolesche Variablen. Zugleich enthält er 20 Dreiecke, also 20 Bedingungen, die gleichzeitig erfüllt werden müssten. Doch das entsprechende Gleichungssystem ist nicht mehr lösbar. Daraus folgt R(3,3) = 6. Die logische Formulierung des Ramsey-Problems mag zwar wie ein überdimensioniertes Rechenverfahren wirken, aber tatsächlich ist es extrem nützlich. Denn für diese Formulierung stehen leistungsfähige Computerprogramme zur Verfügung, sodass man nicht mehr alle Graphen per Hand durchsuchen muss. Ein Beispiel hierfür sind SAT-Solver (SAT steht für satisfiability, also Erfüllbarkeit), die darauf optimiert sind, sehr große boolesche Formeln auf ihre Erfüllbarkeit zu prüfen. Wenn der SAT-Solver eine Lösung findet, liefert er zugleich eine konkrete Färbung ohne einfarbiges Dreieck. Wenn die Gleichungen hingegen unerfüllbar sind, dann ist klar, dass ab dieser Größe des Graphen das gesuchte Muster unvermeidlich ist. Warum ist die Berechnung von Ramsey-Zahlen so aufwendig? Bei der Bestimmung von R(3,3) wirkte das Ramsey-Problem einfach: Man übersetzt die Kanten des Graphen in boolesche Variablen, formuliert für jedes Dreieck eine logische Bedingung und lässt anschließend ein Programm nach zulässigen Lösungen suchen. Allerdings täuscht die Einfachheit. Die Schwierigkeit der Ramsey-Theorie liegt nicht darin, das Problem zu formulieren – im Gegenteil: Kaum ein mathematisches Problem lässt sich so anschaulich erklären. Das Problem liegt vielmehr darin, dass die Zahl der Möglichkeiten mit jedem zusätzlichen Knoten rasant anwächst. Kaum ein mathematisches Problem lässt sich so anschaulich erklären. Das Problem liegt darin, dass die Zahl der Möglichkeiten rasant anwächst Das lässt sich erkennen, wenn man nicht nur nach einfarbigen Dreiecken sucht, sondern nach komplizierteren Strukturen in Graphen. Allgemein bezeichnet R( r, b ) die kleinste Zahl  n, für die jede Rot-Blau-Färbung der Kanten des Graphen K n entweder einen vollständig roten Teilgraphen K r oder einen vollständig blauen Teilgraphen K b enthalten muss. Bei R(4,5) geht es etwa um die Frage, ab welcher Knotenzahl zwangsläufig entweder ein roter K 4 (ein Viereck mit verbundenen Diagonalen) oder ein blauer  K 5 (ein Fünfeck, bei dem alle Knoten miteinander verbunden sind) auftreten muss. Eine Tabelle der bekannten Ramsey-Zahlen zeigt, wie begrenzt das Wissen in diesem Bereich ist. Wenige Werte sind exakt bekannt, für andere kann man nur obere und untere Schranken angeben, also ein Intervall, in dem die Ramsey-Zahl liegen muss. Auffällig ist: Die Zahlen selbst sind nicht besonders groß. Zum Beispiel ist R(4,5) = 25, sodass die Bestimmung wie eine bewältigbare Rechenaufgabe anmutet. Und doch gehört gerade dieser Wert zu den klassischen Beispielen dafür, wie aufwendig exakte Ramsey-Berechnungen werden können. R(4,5) = 25 wurde erst 1995 von den Computerwissenschaftlern Brendan McKay und Stanisław Radziszowski mit umfangreicher Computerunterstützung bewiesen. Der Grund für die Schwierigkeit liegt in der Zahl der möglichen Kantenfärbungen. Ein Graph K n besitzt zwischen jedem Paar seiner n  Knoten genau eine Kante. Die Gesamtzahl der Kanten beträgt daher n ( n −1) / 2. Jede davon kann rot oder blau sein, wodurch es 2 n ( n −1)/2 verschiedene Rot-Blau-Färbungen gibt. Die Zahl wächst folglich exponentiell mit der Anzahl der Kanten. Ein paar zusätzliche Knoten genügen daher schon, um aus einer einfachen Berechnung eine gigantische Suche zu machen. Knoten | Kanten | Färbungen 2 | 1 | 2 3 | 3 | 8 4 | 6 | 64 5 | 10 | 1024 6 | 15 | 32 768 7 | 21 | 2 097 152 8 | 28 | 268 435 456 9 | 36 | 68 719 476 736 10 | 45 | 35 184 372 088 832 11 | 55 | 36 028 797 018 963 968 12 | 66 | 73 786 976 294 838 206 464 13 | 78 | 302 231 454 903 657 293 676 544 14 | 91 | 2 475 880 078 570 760 549 798 248 448 15 | 105 | 40 564 819 207 303 340 847 894 502 572 032 16 | 120 | 1 329 227 995 784 915 872 903 807 060 280 344 576 17 | 136 | 87 112 285 931 760 246 646 623 899 502 532 662 132 736 Natürlich lassen Mathematiker ihre Computer nicht alle diese Färbungen der Reihe nach durchgehen. Die Suche nach Symmetrien und anderen Eigenschaften kann riesige Teile des Suchraums ausschließen. Dennoch bleibt die Schwierigkeit bestehen: Das Problem ist gigantisch. Gerade deshalb ist die Berechnung von R(4,5) = 25 bemerkenswert. Der Graph K 25 besitzt 25⋅24 / 2  = 300 Kanten. Insgesamt gibt es also 2 300 ≈ 2,04⋅10 90 mögliche Färbungen. Diese Zahl ist so groß, dass sie jede naive Suche sinnlos macht. Zum Vergleich: Sie liegt weit über der geschätzten Zahl der Atome im Universum. Dass es trotzdem gelang, zu beweisen, dass jede dieser Färbungen entweder einen roten K 4 oder einen blauen K 5 enthält, ist dem Zusammenspiel aus mathematischer Struktur, geschickter Fallreduktion und umfangreicher Computerunterstützung zu verdanken. Man muss einen riesigen Raum an Möglichkeiten ausschließen Damit wird klar, warum Ramsey-Zahlen bis heute nur lückenhaft bekannt sind. Für eine untere Schranke muss man eine Färbung finden, die das gesuchte Muster vermeidet. Für eine obere Schranke muss man dagegen zeigen, dass keine solche Färbung existiert. Dieser Schritt ist besonders anspruchsvoll: Man muss einen riesigen Raum an Möglichkeiten ausschließen. Die bipartite Ramsey-Zahl BR(2,4) Bislang haben wir nur einen kleinen Teil der Ramsey-Theorie betrachtet. Man kann die Spielregeln verändern und beispielsweise mehr als zwei Farben zulassen oder andere Arten von Graphen betrachten. Fachleute haben sich dabei besonders lange an BR(2,4) die Zähne ausgebissen, einer Ramsey-Zahl für »bipartite« Graphen. Ein solcher Graph besteht aus Knoten, die in zwei getrennte Mengen aufgeteilt sind. Die Kanten dürfen bloß zwischen diesen beiden Mengen verlaufen, niemals innerhalb der Mengen selbst. Übertragen auf das Partybild hieße das: Man betrachtet nicht mehr alle Beziehungen zwischen allen Gästen, sondern nur zwischen zwei Gruppen, etwa den Personen der einen und der anderen Tischseite. Für bipartite Ramsey-Zahlen betrachtet man meist den symmetrischen Fall, bei dem beide Seiten gleich viele Knoten enthalten. Bei der bipartiten Ramsey-Zahl BR(2,4) steht die 2 für das gesuchte einfarbige Muster: einen bipartiten Teilgraphen K 2,2. Dieser besteht aus zwei Knoten auf der linken und zwei Knoten auf der rechten Seite sowie allen vier Kanten, die sie von rechts nach links verbinden. Die zweite Zahl 4 gibt an, dass die Kanten mit vier Farben gefärbt werden. Gesucht ist also die kleinste Zahl  n, für die jede Färbung der Kanten von K n,n mit vier Farben zwangsläufig einen einfarbigen K 2,2 enthält. Dieses Problem lässt sich besonders übersichtlich darstellen. Man kann den vollständigen bipartiten Graphen K n,n als quadratisches Gitter mit n  Zeilen und n  Spalten auffassen. Jede Zeile steht für einen Knoten der einen Seite, jede Spalte für einen Knoten der anderen. Das Feld an der Kreuzung einer Zeile und Spalte entspricht der Kante zwischen den zugehörigen Knoten. Die Farbe des Gitterfelds ist die Farbe dieser Kante. In dieser Darstellung wird aus einem einfarbigen K 2,2  ein einfarbiges Rechteck: Man wählt zwei Zeilen und zwei Spalten. Die vier Schnittpunkte bilden die Ecken eines Rechtecks. Wenn diese vier Gitterpunkte dieselbe Farbe tragen, entspricht das einem einfarbigen Teilgraphen K 2,2. Das bipartite Ramsey-Problem wird damit zu einer scheinbar spielerischen Frage: Wie groß kann ein quadratisches Gitter mit vier Farben sein, ohne dass irgendwo ein gleichfarbiges Rechteck entsteht? Da jedes mögliche Rechteck durch die Wahl von zwei Zeilen und zwei Spalten entsteht, muss man hierfür alle Kombinationen von Zeilenpaaren und Spaltenpaaren berücksichtigen. Damit lässt sich auch BR(2,4) als Erfüllbarkeitsproblem formulieren. Jeder Gitterpunkt kann eine von vier Farben tragen. Vier Möglichkeiten lassen sich mit zwei booleschen Variablen codieren, etwa als 00, 01, 10 und 11. Ein m × n -Gitter benötigt daher 2 mn  boolesche Variablen. Die Bedingungen, die gleichfarbige Rechtecke ausschließen, werden als SAT-Gleichung formuliert. Ist diese erfüllbar, existiert eine rechteckfreie Vierfärbung des Gitters. Fachleute haben viele Gitter, die mit vier Farben koloriert werden, untersucht. Als wir auf dieses Problem aufmerksam wurden, war für die meisten Gittergrößen bekannt, ob es eine rechteckfreie Färbung mit vier Farben gibt. Doch trotz aller Anstrengungen waren sechs Gittergrößen offen: 17×17, 17×18, 18×17, 18×18, 12×21 und 21×12. Da es für 16×16 eine rechteckfreie Färbung gibt, für 19×19 hingegen nicht, musste BR(2,4) zwischen 17 und 19 liegen. Eine direkte Berechnung des 17×17-Gitters schien aussichtslos. Denn schon kleinere Gitter lassen den Suchraum explodieren: Ein 16×16-Gitter enthält 256 Felder, also 512 boolesche Variablen, was 2 512 möglichen Farbmustern entspricht – eine Anzahl, mit der Computer überfordert sind.  Wie sollte man also die Farbmuster für das 17×17- oder das 18×18-Gitter untersuchen? Wir haben uns von der gigantischen Anzahl an Farbmustern nicht abschrecken lassen und mit mehreren Ansätzen versucht, eine Lösung zu finden. Ein wichtiger Schritt bestand darin, nicht den gesamten Suchraum auf einmal zu durchkämmen. Statt jedem Gitterpunkt eine von vier Farben zuzuweisen, fragt man vorläufig nur: Gehört dieser Punkt zu einer bestimmten Farbe oder nicht? Dadurch genügt eine boolesche Variable pro Gitterpunkt. Für ein 18×18-Gitter reduziert sich die Zahl der Variablen dadurch von 648 auf 324. Der Suchraum schrumpft damit von 2 648 ≈ 1,17⋅10 195 auf 2 324 ≈ 3,42⋅10 97. Auch das ist noch astronomisch groß. Aber es macht einen entscheidenden Unterschied: Man sucht nicht mehr unmittelbar nach einer vollständigen Färbung mit vier Farben, sondern nach einer geeigneten Teilstruktur, die man später ergänzen kann. Die Frage lautet zunächst lediglich, wo eine bestimmte Farbe liegen darf, ohne ein einfarbiges Rechteck zu erzeugen. Für diese eine Farbe entsteht eine SAT-Formel, die für jedes Rechteck verbietet, dass alle vier Ecken zu dieser Farbe gehören. Zunächst spuckte uns der SAT-Solver eine triviale Lösung aus, in der keinem Gitterpunkt die gewählte Farbe zugeordnet wird. Auch wenn diese Lösung korrekt ist, bringt sie uns nicht weiter. Darum haben wir als weitere Bedingung eingeführt, dass ein Viertel der 324 Gitterpunkte der einen Farbe entsprechen soll. Für diesen Fall gelang es, eine rechteckfreie Zuordnung zu schaffen. Als Nächstes wollten wir dem Problem eine zweite Farbe hinzufügen, die 81 der noch nicht eingefärbten Gitterpunkte zugeordnet wird – natürlich ohne dass ein einfarbiges Rechteck entsteht. Dieser Schritt scheiterte jedoch an der Belegung der Gitterpunkte durch die erste Farbe. Also starteten wir einen neuen Versuch. Hierfür teilten wir die 324 Gitterpunkte in 81 Bereiche von je vier Punkten auf. Eine logische Klausel sicherte hierbei ab, dass jedem Gitterpunkt innerhalb eines Bereichs je eine Farbe zugeordnet wird. Darüber hinaus stellte eine weitere Klausel sicher, dass eine Farbe nicht doppelt innerhalb des Bereichs auftaucht. Auf diese Weise erhält man 23 976 Klauseln, die gelöst werden müssen.  Als wir diese einem gewöhnlichen PC übergaben, waren wir sehr erfreut, nach etwas mehr als sieben Stunden ein Ergebnis gefunden zu haben: Der SAT-Solver hatte eine rechteckfreie Färbung des 18×18-Gitters entdeckt. Damit war bewiesen, dass BR(2,4) = 19 ist. Dieses Beispiel zeigt, weshalb manche kombinatorischen Probleme so tückisch sind. Sie lassen sich in wenigen Sätzen erklären, aber nicht dadurch lösen, dass man sie einfach vollständig durchrechnet. Mathematische Intuition erkennt vielversprechende Einschränkungen; der Computer prüft anschließend gewaltige Fallmengen Ein Computer, der ohne zusätzliche Struktur durch den gesamten Suchraum läuft, scheitert an der schieren Zahl der Möglichkeiten. Ein Mensch wiederum kann die Milliarden und Abermilliarden von Einzelfällen nicht allein überblicken. Der Durchbruch liegt in der Verbindung beider Fähigkeiten: Mathematische Intuition erkennt Muster, Symmetrien und vielversprechende Einschränkungen; der Computer prüft anschließend gewaltige Fallmengen, die für Menschen unzugänglich sind. Damit zeigen Ramsey-Probleme, wie moderne Mathematik heute funktionieren kann: Ein anschaulich formulierbares Problem wird in Logik übersetzt, mit Computerhilfe untersucht und durch menschliche Einsicht so weit strukturiert, dass die Maschine überhaupt eine Chance bekommt. Weder der Mensch noch der Computer allein reicht aus. Erst gemeinsam verwandeln sie eine scheinbar unüberschaubare Menge möglicher Welten in einen mathematischen Beweis.