Warum ist Zufälligkeit ein Problem? (dh warum interessiert uns die Derandomisierung?)
7
Ich lese Aaronsons Umfrage zu P vs. NP und habe verstanden, dass sich die Leute in der CS-Theorie wirklich für Derandomisierungsergebnisse wie P vs. BPP usw. interessieren. Meine Frage ist, was ist das Problem mit der Zufälligkeit? Wenn bekannt ist, dass Ihr Algorithmus nur eine Polynomzahl von Zufallsbits benötigt, bitten Sie einfach einen Physiker, die Bits für Sie zu besorgen. Dies ist kein Problem, da Sie nur eine nachvollziehbare Anzahl von Bits benötigen, und schreiben Sie sie dann auf die Turing Maschinenband und du bist gut! Das Ziel der Komplexitätstheorie ist es herauszufinden, was wir in diesem Universum berechnen können, oder? Nun, dieses Universum hat Zufälligkeit, oder? Warum interessiert uns die Derandomisierung? Theoretische und praktische Antworten sind willkommen.
Die Komplexitätstheorie ist eine mathematische Theorie, die darauf abzielt, einen Mangel der Berechenbarkeitstheorie zu beheben, nämlich den Einsatz von Ressourcen zu berücksichtigen. Zwar zielte es in seinen Anfängen darauf ab, den Begriff der "praktischen Berechnung" zu erfassen (selbst bestimmte Geschmacksrichtungen wie die parallele Berechnung, die angeblich von NC erfasst wurde), doch ist er seitdem auseinander gerutscht und von der Realität abgewichen. Als Beispiel können Sie höhere Schritte in der Polynomhierarchie, Klassen mit höherer Komplexität wie PSPACE, Klassen, die mithilfe von Alternation definiert wurden, usw. ausführen. Tatsächlich stammt ein Großteil dieses Materials aus den Anfängen der Komplexitätstheorie und zeigt, dass es ziemlich schnell den Kontakt zur Realität verloren hat.
Traditionell sind die beiden wichtigsten Ressourcen, die von der Komplexitätstheorie untersucht werden, Zeit und Raum. Andere Ressourcen haben jedoch auch Komplexitätstheoretiker interessiert, zum Beispiel Alternation und Zufälligkeit (ganz zu schweigen von der Welt der Schaltungskomplexität). Philosophisch gesehen ist es eine faszinierende Frage, ob Zufälligkeit die Rechenzeit einiger Probleme dramatisch verkürzt oder ob die Verstärkung nur polynomisch ist (wie durch die Vermutung P = BPP angedeutet). Es scheint jedoch keine praktische Relevanz zu haben, allerdings nicht aus dem von Ihnen genannten Grund. In der Praxis besteht keine Notwendigkeit für eine tatsächliche physische Zufälligkeit (außer für kryptografische Zwecke), und Pseudozufallszahlengeneratoren funktionieren gut genug.
Ich würde jedoch hinzufügen, dass praktisch in diesen Fällen "echte" Zufälligkeit erforderlich ist, es tatsächlich nützlich ist, sie zu minimieren, da das Sammeln von Entropie relativ langsam ist.
Derek Elkins verließ SE
2
Ich bin kein Spezialist für Komplexitätstheorie, aber ich denke, es gibt einige praktische Gründe, sich für diese Frage zu interessieren.
Wie Derek Elkins bemerkte, ist es ziemlich schwierig, tatsächlich "physische" Zufallszahlen zu erzeugen, und es ist schwierig genug, die richtige Verteilung mit der richtigen Entropiemenge bei ausreichender Geschwindigkeit zu erzeugen, um Websites und benutzerdefinierte Hardware zu rechtfertigen . Es wäre schön zu wissen, dass dies zumindest theoretisch vermieden werden kann.
In der klassischen Physik gibt es keine "wahre" Zufälligkeit, nur die (deterministischen) physikalischen Gesetze und die Anfangsbedingungen des Systems (oder des gesamten Universums, denke ich). Es ist eine interessante philosophische Frage, ob diese Zufälligkeit in gewissem Sinne der wahren Zufälligkeit entspricht. Diese Frage findet Antworten in den Bereichen Chaostheorie , Ergodentheorie und Informatik in Fragen wie P vs BPP.
Die Frage, ob wir die Zufälligkeit in P gegen BPP genau simulieren können, scheint sehr verwandt mit der Frage zu sein, ob wir wirklich Verschlüsselung durchführen können, beispielsweise die Existenz von Falltür- oder Einwegfunktionen . Insbesondere scheint die Fähigkeit, Bits deterministisch zu erzeugen, die für einen bestimmten Algorithmus "zufällig" genug aussehen, eine gute Voraussetzung zu sein, um eine kryptografische Funktion zu finden, die eine bestimmte Nachricht in einen von zufälligen Bits nicht unterscheidbaren Bitstrom verschlüsselt, wenn der Schlüssel nicht bekannt ist . Die Lösung der sehr schwierigen Frage nach der Existenz von Einwegfunktionen sollte daher die Lösung von P gegen BPP auf dem Weg erfordern.
1. Zeigt random.org nicht tatsächlich, dass die Erstellung physischer Zufallszahlen so schnell ist, dass ein Mann genug davon machen kann, um das gesamte Internet zu versorgen? 2. Unser derzeit bestes Modell der Atomphysik ist die Quantenmechanik, die an sich zufällig ist. Die klassische Physik kann nicht einmal anfangen, Dinge wie Schwarzkörperstrahlung oder den photoelektrischen Effekt zu erklären.
David Richerby
@DavidRicherby: 1. die Zahlen deuten darauf hin , 165,2 giga Bits über 9 Jahre , die wie so viel scheint nicht (schon gar nicht genug für die ganze Internet, sagen , wenn sie als Nonces für Krypto - Zwecke verwendet wurden). 2. Ich denke, die Jury ist immer noch etwas offen für QM und "echte Zufälligkeit" (obwohl afaik, scheint QM eine Quelle rein probabilistischer Informationen zu sein). Die Frage für die klassische Mechanik ist jedoch immer noch von Interesse, da wir in Bezug auf Computer und "alltägliche" Physik in einer klassischen Welt leben.
Ich bin kein Spezialist für Komplexitätstheorie, aber ich denke, es gibt einige praktische Gründe, sich für diese Frage zu interessieren.
Wie Derek Elkins bemerkte, ist es ziemlich schwierig, tatsächlich "physische" Zufallszahlen zu erzeugen, und es ist schwierig genug, die richtige Verteilung mit der richtigen Entropiemenge bei ausreichender Geschwindigkeit zu erzeugen, um Websites und benutzerdefinierte Hardware zu rechtfertigen . Es wäre schön zu wissen, dass dies zumindest theoretisch vermieden werden kann.
In der klassischen Physik gibt es keine "wahre" Zufälligkeit, nur die (deterministischen) physikalischen Gesetze und die Anfangsbedingungen des Systems (oder des gesamten Universums, denke ich). Es ist eine interessante philosophische Frage, ob diese Zufälligkeit in gewissem Sinne der wahren Zufälligkeit entspricht. Diese Frage findet Antworten in den Bereichen Chaostheorie , Ergodentheorie und Informatik in Fragen wie P vs BPP.
Die Frage, ob wir die Zufälligkeit in P gegen BPP genau simulieren können, scheint sehr verwandt mit der Frage zu sein, ob wir wirklich Verschlüsselung durchführen können, beispielsweise die Existenz von Falltür- oder Einwegfunktionen . Insbesondere scheint die Fähigkeit, Bits deterministisch zu erzeugen, die für einen bestimmten Algorithmus "zufällig" genug aussehen, eine gute Voraussetzung zu sein, um eine kryptografische Funktion zu finden, die eine bestimmte Nachricht in einen von zufälligen Bits nicht unterscheidbaren Bitstrom verschlüsselt, wenn der Schlüssel nicht bekannt ist . Die Lösung der sehr schwierigen Frage nach der Existenz von Einwegfunktionen sollte daher die Lösung von P gegen BPP auf dem Weg erfordern.
quelle