- Theoretische Informatiker nutzen hypothetische Orakel zur sofortigen und fehlerfreien Beantwortung spezifischer Fragen. Orakel können Beziehungen zwischen verschiedenen Komplexitätsklassen aufzeigen und bieten Einblicke in Fragen wie P vs. NP. In einer Welt mit Orakeln wären P und NP möglicherweise gleich, was massive Auswirkungen auf Verschlüsselung hätte. Diagonalisierung reicht nicht aus, um das P-gegen-NP-Problem zu lösen, da Orakel die Ergebnisse verändern können. Orakel spielen auch im Quantencomputing eine Rolle und helfen, die Schwierigkeit bestimmter Probleme besser zu verstehen.
Fragen Sie eine magische 8-Ball-Kugel, und sie wird Ihnen mit Ja, Nein oder einer lästig unentschiedenen Antwort antworten. Wir mögen sie als Kinderspielzeug betrachten, jedoch nutzen theoretische Informatiker ein ähnliches Instrument. Sie stellen sich hypothetische Geräte vor, sogenannte Orakel, die in der Lage sind, spezifische Fragen sofort und fehlerfrei zu beantworten. Diese fantasievollen Gedankenexperimente haben neue Algorithmen inspiriert und Forschern geholfen, die Landschaft der Berechnung zu kartieren. Die Forscher, die Orakel heraufbeschwören, arbeiten in einem Teilgebiet der Informatik namens Komplexitätstheorie. Sie beschäftigen sich mit der inhärenten Schwierigkeit von Problemen, wie zum Beispiel der Bestimmung, ob eine Zahl eine Primzahl ist oder der Suche nach dem kürzesten Weg zwischen zwei Punkten in einem Netzwerk.
Der unlösbare Konflikt
Einige Probleme lassen sich einfach lösen, andere scheinen weitaus schwieriger, bieten jedoch Lösungen, die sich einfach überprüfen lassen, während wieder andere einfach für moderne Computer zu sein scheinen, aber für herkömmliche schwer. Komplexitätstheoretiker wollen verstehen, ob diese scheinbaren Schwierigkeitsunterschiede fundamental sind. Ist eine Aufgabe von Natur aus kompliziert, oder fehlt uns nur die Raffinesse für eine gute Lösung? Forscher adressieren solche Fragen, indem sie Probleme in verschiedene Klassen einsortieren—alle einfachen Aufgaben kommen in eine Klasse, zum Beispiel, und alle einfach zu überprüfenden Aufgaben in eine andere—und beweisen Theoreme über die Beziehungen zwischen diesen Klassen.
Eine der größten Herausforderungen war das Abbilden der Landschaft der Berechnungsschwierigkeiten. In den 1970er Jahren begannen einige Forscher zu untersuchen, was passieren würde, wenn die Regeln der Berechnung anders wären. Hier kommen Orakel ins Spiel. Wie die magischen 8-Balls sind Orakel Geräte, die Ja- oder Nein-Fragen sofort beantworten, ohne etwas über ihren inneren Mechanismus preiszugeben. Anders als die magischen 8-Balls geben sie stets korrekt Antwort—ein Vorteil, weil sie fiktional sind. Jedes Orakel beantwortet spezifische Fragen, wie etwa „Ist diese Zahl prim?“.
Die Rolle der Orakel
Was macht diese fiktionalen Geräte nützlich für das Verständnis der realen Welt? Kurz gesagt, sie können versteckte Zusammenhänge zwischen verschiedenen Komplexitätsklassen aufzeigen. Nehmen Sie die zwei bekanntesten Klassen: die der Probleme, die leicht zu lösen sind, die Forscher „P“ nennen, und die der Probleme, die sich leicht überprüfen lassen, die „NP“ genannt werden. Sind alle einfach zu überprüfenden Probleme auch leicht zu lösen? Wenn ja, würde das bedeuten P wäre gleich NP, und alle Verschlüsselung würde zusammenbrechen (nebst anderen Konsequenzen). Komplexitätstheoretiker vermuten, dass NP nicht gleich P ist, doch können sie es nicht beweisen, obgleich sie versuchen, die Beziehung zwischen diesen beiden Klassen festzulegen.
Orakel haben ihnen geholfen, ein besseres Verständnis dessen zu erlangen, womit sie arbeiten. Forscher haben Orakel entwickelt, die Fragen beantworten, die zur Lösung vieler verschiedener Probleme beitragen. In einer Welt, in der jeder Computer eine direkte Verbindung zu einem dieser Orakel hätte, wären alle leicht zu überprüfenden Aufgaben auch einfach zu lösen, und P wäre gleich NP. Andere, weniger hilfreiche Orakel hätten den gegensätzlichen Effekt. In einer solchen Welt wären P und NP nachweislich verschieden. Forscher haben dieses Wissen genutzt, um sich ein besseres Bild vom P-gegen-NP-Problem zu machen.
Orakel und Quantenrechnungen
Die ersten Versuche, die Beziehung zwischen P und NP zu bestimmen, nutzten einen eleganten Trick namens Diagonalisierung, der für andere bedeutende Ergebnisse in der Informatik von entscheidender Bedeutung war. Aber Forscher stellten bald fest, dass jeder Beweis, der auf der Diagonalisierung basiert, auch für jede Welt gelten würde, in der jeder Computer dasselbe Orakel konsultieren kann. Dies bedeutete das Aus, da Orakel die Antwort auf die P-gegen-NP-Frage ändern. Wenn Forscher mittels Diagonalisierung beweisen könnten, dass P und NP in der realen Welt unterschiedlich sind, würde der gleiche Beweis darauf hindeuten, dass P und NP in einer Welt mit Orakeln verschieden sind, wo sie doch eindeutig gleichwertig sind. Das bedeutet, dass jede diagonalisationbasierte Lösung des P-gegen-NP-Problems widersprüchlich wäre. Forscher kamen zu dem Schluss, dass sie neue Techniken benötigen, um Fortschritte zu erzielen.
Orakel waren auch im Bereich der Quantencomputing-Studien nützlich. In den 1980er und 1990er Jahren entdeckten Forscher, wie man die Quantenphysik nutzen könnte, um schnell bestimmte Probleme zu lösen, die für gewöhnliche „klassische“ Computer schwer zu sein schienen. Aber schienen diese Probleme nur schwierig zu sein, oder waren sie es wirklich? Um dies letztlich zu beweisen, wären radikal neue mathematische Techniken erforderlich.
