Stellen Sie sich vor, Sie möchten die Natur der Berechnung verstehen. Du bist tief in der Wildnis, fernab jeglicher Wege, und unergründlich Nachrichten sind in die Baumstämme um Sie herum eingraviert – BPP, AC⁰[m], Σ₂P, YACC und Hunderte andere. Die Glyphen wollen Ihnen etwas sagen, aber wo soll ich anfangen? Man kann sie nicht einmal alle gerade halten.

Nur wenige Forscher haben so viel getan Russel Impagliazzo um dieses scheinbare Chaos zu durchbrechen. Seit 40 Jahren arbeitet Impagliazzo an der Spitze der rechnerischen Komplexitätstheorie, der Untersuchung der intrinsischen Schwierigkeit verschiedener Probleme. Die bekannteste offene Frage in diesem Bereich, das so genannte P-NP-Problem, fragt, ob viele scheinbar schwierige Rechenprobleme tatsächlich einfach sind – mit dem richtigen Algorithmus. Eine Antwort hätte weitreichende Auswirkungen auf die Wissenschaft und die Sicherheit der modernen Kryptographie.

In den 1980er und 1990er Jahren spielte Impagliazzo eine führende Rolle bei der Vereinigung Theoretische Grundlagen der Kryptographie. 1995 brachte er die Bedeutung dieser neuen Entwicklungen in einem ikonischen Aufsatz zum Ausdruck, in dem er mögliche Lösungen für P versus NP und eine Handvoll damit zusammenhängender Probleme in der Sprache von neu formulierte fünf hypothetische Welten Wir könnten bewohnen, skurrilerweise Algorithmica, Heuristica, Pessiland, Minicrypt und Cryptomania genannt. Die fünf Welten von Impagliazzo haben eine Generation von Forschern inspiriert und sie leiten weiterhin die Forschung auf dem florierenden Teilgebiet Metakomplexität.

Und das sind nicht die einzigen Welten, die er sich ausgedacht hat. Impagliazzo ist ein lebenslanger Fan von Tabletop-Rollenspielen wie Dungeons and Dragons und hat Freude am Erfinden neue Regelwerke und neue Umgebungen zum Erkunden. Derselbe spielerische Geist belebt seine 30-jährige Praxis der Improvisationskomödie.

Impagliazzo leistete auch grundlegende Arbeiten zur Aufklärung der grundlegenden Rolle des Zufalls bei der Berechnung. In den späten 1970er Jahren entdeckten Informatiker, dass der Zufall manchmal dazu in der Lage ist Algorithmen verbessern zur Lösung inhärent deterministischer Probleme – eine kontraintuitive Erkenntnis, die Forscher jahrelang verwirrte. Impagliazzos Arbeit mit dem Komplexitätstheoretiker Avi Wigderson und andere Forscher zeigten in den 1990er Jahren, dass bestimmte Rechenprobleme, wenn sie wirklich grundsätzlich schwierig sind, dann auch so sind immer möglich um Algorithmen, die Zufälligkeit verwenden, in deterministische umzuwandeln. Und umgekehrt, der Beweis, dass Zufälligkeit aus jedem Algorithmus eliminiert werden kann würde auch beweisen dass es wirklich schwierige Probleme gibt.

Wie viel sprach mit Impagliazzo über den Unterschied zwischen schwierigen Problemen und schweren Rätseln, das Befragen von Orakeln und die mathematischen Lehren der Improvisationskomödie. Das Interview wurde aus Gründen der Klarheit gekürzt und bearbeitet.

Wann haben Sie sich zum ersten Mal für Mathematik interessiert?

Ich interessierte mich schon für Mathematik, bevor ich wirklich wusste, was es ist. In der dritten Klasse begannen meine Mathenoten zu schwächeln, weil wir unsere Multiplikationstabellen auswendig lernen sollten, und ich weigerte mich. Meine Mutter sagte: „Aber Russell, du liebst Mathe, warum machst du das nicht?“ Und ich sagte: „Das ist keine Mathematik, das ist Auswendiglernen.“ Echte Mathematik erfordert kein Auswendiglernen.“ Alles, was ich zu diesem Zeitpunkt gelernt hatte, war Rechnen, daher bin ich mir nicht sicher, woher ich die Vorstellung hatte, dass es in der Mathematik um abstrakte Konzepte geht.

Was ist mit Informatik? Teile des Fachgebiets sind sehr abstrakt, aber sie sind nicht das, was den meisten Menschen zuerst begegnet.

In der High School hatte ich einen Programmierkurs in BASIC besucht, aber es war wirklich schwer, etwas zu schaffen. Die Programme mussten auf Papierbänder übertragen werden, die über diesen sehr alten Computer laufen mussten, der oft nicht richtig funktionierte und das Papier in zwei Hälften riss. Deshalb fand ich Informatik furchtbar langweilig.

Ich hatte vor, Logik zu studieren. Aber viele der Konzepte erforderten, wenn man versuchte, sie tatsächlich zu formalisieren, Berechnungen und insbesondere Einschränkungen bei der Berechnung. Fragen wie „Woher wissen wir, dass Dinge in der Mathematik wahr sind?“ und „Wie verstehen wir die Schwierigkeit, Mathematik zu betreiben?“ führte zur theoretischen Informatik und insbesondere zur Komplexitätstheorie.

Einige Ihrer berühmtesten Arbeiten untersuchen die Zusammenhänge zwischen Kryptographie und rechnerischer Komplexitätstheorie. Warum hängen diese beiden Bereiche zusammen?

Wenn Sie ein kryptografisches System einrichten, müssen Sie zwischen legitimen Benutzern – den Personen, denen Sie Zugriff gewähren möchten – und allen anderen unterscheiden. Rechentechnisch schwierige Probleme geben uns die Möglichkeit, diese Gruppen anhand ihres Wissens zu unterscheiden. Wenn Sie aber wollen, dass die Antwort auf ein Problem eine Möglichkeit ist, zwei Gruppen von Menschen zu unterscheiden, können Sie nicht einfach irgendein schwieriges Problem verwenden – Sie brauchen ein schwieriges Rätsel.

Was ist der Unterschied zwischen einem Problem und einem Rätsel?

Im Allgemeinen kennt die Person, die ein Problem stellt, die Antwort möglicherweise nicht. Ein Puzzle ist ein Problem, das mit einer Antwort im Hinterkopf entworfen wurde. Warum brauchen wir also ein Puzzle? Denn wir müssen feststellen können, ob die Person, die das Problem angeblich gelöst hat, es tatsächlich gelöst hat. Im Alltag verwenden wir Rätsel zur Unterhaltung, aber auch im Klassenzimmer nutzen wir sie, um zu testen, ob die Leute den Stoff verstanden haben. Das passiert in der Kryptographie: Wir verwenden Rätsel, um das Wissen einer Person zu testen.

Der Unterschied zwischen den fünf Welten besteht darin, wie sie die Fragen „Gibt es schwierige Probleme?“ beantworten. und „Gibt es schwierige Rätsel?“

Wie wirken sich diese unterschiedlichen Antworten aus?

In der ersten Welt, Algorithmica, sind keine Probleme schwer. Sie müssen nicht wissen, wie jemand Ihr Problem entworfen hat: Sie können es immer lösen. Heuristica sagt: „Na ja, vielleicht sind ein paar Probleme schwierig.“ Dann kommen wir nach Pessiland, wo viele Probleme schwierig sind, die meisten Rätsel jedoch nicht. Bei fast jedem Problem, das ich mir ausdenke, und bei dem ich die Lösung kenne, wirst du es auch lösen können. Alle diese Welten sind schlecht für die Kryptographie.

In Minicrypt kann ich Rätsel erstellen, die ich zu lösen weiß und die dennoch eine echte Herausforderung für Sie darstellen. Und schließlich ist Cryptomania eine Welt, in der zwei Menschen an einem öffentlichen Ort stehen können, wo ein Lauscher zuhören kann, und gemeinsam ein Rätsel lösen können, das für den Lauscher immer noch schwierig ist.

Was hat Sie dazu motiviert, den Artikel über die fünf Welten zu schreiben?

Damals war bekannt, dass unterschiedliche Antworten auf die P- oder NP-Frage einen großen Einfluss darauf haben würden, welche Art von Problemen wir lösen können und auch auf welche Art von Sicherheit wir hoffen können, aber die qualitativen Unterschiede zwischen verschiedenen Formen der Leichtigkeit und Härte waren nicht wirklich klar.

Nur ein paar Jahre zuvor gab es ein sehr aufschlussreiches Papier, in dem die Unterschiede anhand vieler miteinander verbundener Fragen mit etwa 20 möglichen Antworten dargelegt wurden. Ein Grund, warum ich den Artikel über die fünf Welten schreiben wollte, war, dass wir in diesen wenigen Jahren große Fortschritte gemacht hatten. Es wäre schwierig gewesen, Namen für 20 mögliche Welten zu finden.

Warum sollte man es also so darstellen, als unterschiedliche Welten mit skurrilen Namen?

Ich hatte zugestimmt, diesen Aufsatz für eine Konferenz zu schreiben. Ich blieb bis spät in die Nacht wach und versuchte herauszufinden, was ich sagen sollte, und gegen 1 Uhr morgens schien es mir eine gute Idee zu sein, die verschiedenen Welten einzuordnen. Und dann las ich es am nächsten Morgen und es schien immer noch eine gute Idee zu sein – es war eine Möglichkeit zu zeigen, wie diese Ideen tatsächlich die Welt beeinflussen würden, ohne sich in quantitativen Details zu verlieren. Was mich an dieser Arbeit am meisten freut, ist, dass ich von Leuten, die sich mit Komplexitätsforschung befassen, höre, dass dies die Arbeit war, die sie als Studenten für das Fachgebiet interessiert hat.

Haben Forscher eine der fünf möglichen Welten ausgeschlossen?

Wir fügen tatsächlich noch mehr hinzu – die Leute haben angefangen, darüber zu reden Obfustopie als eine Welt noch stärkerer kryptografischer Tools. Es ist ein wenig deprimierend, dass wir Ende der 1980er Jahre so große Fortschritte gemacht haben und seitdem keine Welten eliminiert haben. Aber andererseits wissen wir viel mehr über die Zusammenhänge zwischen den Welten und haben eine viel klareres Bild davon, wie jede Welt aussehen würde.

Hypothetische Welten spielen auch in der Komplexitätstheorie eine weitere Rolle, nämlich in Beweisen, die die Existenz von „Orakeln“ annehmen. Was genau ist also ein Orakel?

Stellen Sie sich vor, jemand baut ein geniales Gerät, das ein Problem lösen kann, ohne dass wir einen Algorithmus zur Lösung dieses Problems kennen. Das ist es, was ein Orakel ist. Wenn wir solch ein wundersames Gerät hätten und es in unseren Computer einbauen würden, könnte es die Grenze zwischen dem, was berechenbar ist, und dem, was nicht berechenbar ist, verschieben.

Glauben Forscher, dass diese Zauberkästen tatsächlich existieren könnten?

Nein, sie existieren wahrscheinlich nicht. Anfangs waren die Ergebnisse von Oracle etwas umstritten, weil sie so hypothetisch waren. Sie können jedoch sehr aufschlussreich sein, wenn das Orakel zur Modellierung einer idealen Situation verwendet wird. Angenommen, Sie versuchen zu zeigen, dass A nicht unbedingt B impliziert. Sie beginnen mit der Einstellung, in der Sie das extremste A haben, und zeigen, dass dies immer noch nicht ausreicht, um B zu garantieren. Wenn Sie das zeigen können, auch wenn alle Chancen gut sind Zu Ihren Gunsten können Sie immer noch nichts beweisen, das ist wirklich ein starker Beweis dafür, dass es schwierig sein wird, es zu beweisen.

Sie haben auch Zusammenhänge zwischen Rechenhärte und Zufälligkeit entdeckt. Wie funktioniert diese Verbindung?

Es ist eigentlich eine Art zu sagen, dass etwas, das man nicht versteht, zufällig erscheinen kann. Angenommen, ich sage, ich denke an eine Zahl zwischen eins und tausend. Wenn ich die Zahl zufällig auswähle, haben Sie eine Chance von eins zu tausend, sie zu erraten. Und wenn ich – in Anlehnung an Monty Python – frage: „Wie hoch ist die durchschnittliche Fluggeschwindigkeit einer europäischen Schwalbe in Meilen pro Stunde?“ Du hast ungefähr die gleichen Chancen. Es fährt wahrscheinlich mehr als eine Meile pro Stunde, und wahrscheinlich nicht mehr als tausend Meilen pro Stunde.

Das ist eigentlich kein Zufall – es ist eine deterministisch beantwortbare Frage. Wir könnten einfach alle umherfliegenden Schwalben messen, aber das lässt sich mit begrenzten Ressourcen nur schwer bestimmen, zum Beispiel weil wir kein Budget für die Messung der Schwalbengeschwindigkeit haben und nicht über einen unendlichen Vorrat an Schwalben verfügen.

Die Erkenntnis ist also, dass schwierige Probleme, deren Lösungen wir nicht kennen, eine Quelle für „pseudozufällige“ Zahlen sein können, die zufällig aussehen.

Apropos Monty Python: Ich weiß, dass Sie schon lange Improvisationskomödie machen – wie haben Sie angefangen?

Ich habe 1991 als Assistenzprofessorin in San Diego angefangen. Und ungefähr im Jahr 94 dachte ich: „Ich habe wirklich kein großes Leben außerhalb der Abteilung.“ Also besorgte ich mir die kostenlose Wochenzeitung und schaute mir die Liste der Vereine und Aktivitäten an. Ich habe alles außer der Improvisationskomödie gestrichen – ich hielt es zumindest für plausibel, dass ich damit klarkommen würde. Ich habe meine Frau in diesem Anfängerkurs kennengelernt.

Was dachte sie?

Sie sagt, ich war wirklich schrecklich. Wenn Sie ein Logiker sind, sind Sie darauf trainiert, immer über die Nuancen jedes Wortes nachzudenken. Du willst nichts Falsches sagen. Improvisieren ist insofern großartig, als es das Gegenteil umkehrt: Es geht nicht darum, etwas Perfektes zu sagen, sondern darum, schnell etwas zu erfinden. Es war das Gegenteil vom Rest meines Lebens.

Meine jetzige Frau machte eine Pause vom Unterricht, und als sie ein Jahr später zurückkam, gelang es mir, sie zu beeindrucken. Das war vor 30 Jahren. Ich besuche immer noch denselben Kurs mit demselben Lehrer.

Hat Improvisation Ihre Herangehensweise an Ihre Forschung verändert?

Es ist eine gute Übung, nicht bei jedem Gedanken, den Sie haben, überkritisch zu sein. Das ist besonders hilfreich bei Kooperationen. Wenn ich mit anderen Menschen zusammenarbeitete, sagte ich immer Dinge wie: „Aber diese Idee wird aus folgendem Grund nicht funktionieren.“ Das ist nicht wörtlich wahr.“ Beim Improvisieren solltest du immer akzeptieren, was dein Partner sagt. Und ich denke, das ist eine gute Einstellung, insbesondere wenn man mit Studierenden recherchiert: Lehne etwas, das sie sagen, nicht ab, nur weil du weißt, dass es falsch ist. Es gibt viele gute Ideen, die nicht zu 100 % richtig sind.

Wie was?

Wenn Sie versuchen, eine Intuition für ein Problem zu entwickeln, hilft es, mit einigen vereinfachenden Annahmen zu beginnen. Diese Annahmen sind normalerweise nicht wahr, aber sie können Ihnen bei der Erstellung einer Roadmap helfen. Sagen Sie: „Wenn ich einen Elefanten hätte, könnte ich die Berge überwinden.“ Natürlich habe ich keinen Elefanten. Aber wenn ich es täte, würde ich es so machen.“ Und dann wird einem klar: „Vielleicht brauche ich für diesen Schritt keinen Elefanten.“ Ein Maultier wäre in Ordnung.“

Wie steht es mit Ihrer Liebe zu Rollenspielen – hat das Ihre Arbeit überhaupt beeinflusst?

Es hat vielleicht nicht alle meine Forschungen beeinflusst, aber es hat sicherlich meine Arbeit über die fünf Welten beeinflusst. Ich hatte schon immer ein allgemeines Interesse an Fantasy und Science-Fiction und daran, mir verschiedene mögliche Welten auszudenken – wie wäre es, wenn alles anders wäre?

Warum sind Rollenspiele eine so überzeugende Möglichkeit, hypothetische Welten zu erkunden?

Menschen, die sich für spekulative Fiktion interessieren, haben schon immer Welten erfunden. Tolkien ist vor allem dafür berühmt, und er hatte eine so gewaltige Vorstellungskraft, dass sich seine Welt tatsächlich belebt anfühlte. Für diejenigen von uns, die nicht so einfallsreich sind: Der beste Weg, dies zu erreichen, besteht darin, Leute in die eigene Umgebung und ein Spiel einzuladen ist eine Möglichkeit, das zu tun. Jetzt ist es nicht nur meine Welt. Es hat vielleicht so angefangen, wie ich es mir vorgestellt habe, aber wie bei jeder Zusammenarbeit hat es sich aufgrund der Beiträge aller anderen weit darüber hinaus entwickelt.