Verwendung negativer Ergebnisse zum Nachweis positiver Ergebnisse in der Berechenbarkeitstheorie

Viele Ergebnisse in der Kryptographie hängen von Unmöglichkeitsergebnissen / Vermutungen in der Komplexitätstheorie ab. Beispielsweise wird angenommen, dass die Kryptographie mit öffentlichem Schlüssel unter Verwendung von RSA aufgrund der Vermutung über die Unmöglichkeit des Factorings (und der modularen Root-Finding-Probleme) möglich ist.

Meine Frage ist :

Haben wir ähnliche Ergebnisse in der Berechenbarkeitstheorie? Gibt es interessante positive Konstruktionen mit negativen Unmöglichkeitsergebnissen?

Ermöglicht uns die Unentscheidbarkeit des Stoppproblems beispielsweise, Aufgaben auszuführen, die wir nicht ausführen könnten, wenn das Stoppproblem entscheidbar wäre?

cc.complexity-theory cr.crypto-security computability Kaveh
quelle

Zwei Hauptanwendungen von Negativitätsergebnissen in der Komplexitätstheorie sind (1) Kryptographie und (2) Derandomisierung. Beides gilt nicht für das Berechenbarkeits-Framework. Das Entschlüsseln eines berechenbaren Kryptosystems ist unweigerlich eine berechenbare Aufgabe, und jede auf einer zufälligen Turing-Maschine berechenbare Funktion ist auch auf einer deterministischen Turing-Maschine (auf konstruktive Weise) berechenbar.

David Harris

Dies scheint eine Frage der Formulierung zu sein. "Kryptographie mit öffentlichem Schlüssel unter Verwendung von RSA ist möglich" ist nur die halb volle Art zu sagen, "RSA in Poly-Time zu knacken ist unmöglich". Ich sehe nicht, wie RSA eine positive Konstruktion ist ... es ist nur eine Konstruktion, und ihr Sicherheitsnachweis ist ein negatives Ergebnis über mögliche gegnerische Algorithmen.

Artem Kaznatcheev

@Artem, hier geht es darum, dass wir ein Protokoll erstellen, das verwendet werden kann, und die Bedingung, dass das Protokoll nützlich ist, ist ein negatives Ergebnis, dass es keine Gegner gibt, die es brechen können. Intuitiv meine ich mit einem negativen Ergebnis einen Satz, der besagt, dass etwas nicht getan werden kann. Mit einem positiven Ergebnis meine ich eine Konstruktion, die es ermöglicht, eine Aufgabe auszuführen (z. B. sichere Kommunikation). Ein positives Ergebnis kann ein negatives Ergebnis enthalten. Ich werde darüber nachdenken, dies formeller auszudrücken.

Kaveh

@ David, ja, ich bin mir dieser beiden bewusst. Kennen Sie eine andere bekannte Verwendung der negativen Ergebnisse für positive Ergebnisse in der Komplexitätstheorie / Krypto?

Kaveh

Ich persönlich denke auch, dass es eine Frage der Formulierung ist. Zum Beispiel können Sie den Rice-Satz nehmen und sagen: "Für jedes Antivirus können Sie einen Virus konstruieren, der nicht erkannt wird." In jedem Unvollständigkeitssatz können Sie ihn in "Sie können ein Gegenbeispiel konstruieren" umwandeln.

Ludovic Patey

Antworten:

In gewissem Sinne geht es in der Parametrizitätstheorie darum.

Durch Datenabstraktion stellen wir sicher, dass kein Client eines Moduls auf die Elemente eines Moduls zugreifen kann, außer gemäß der vom Modul bereitgestellten Schnittstelle. Wir verlassen uns darauf, um sicherzustellen, dass die internen Invarianten von Datenstrukturen von den Clients eines Moduls nicht gebrochen werden können. Wenn Sie beispielsweise nur über die veröffentlichte Schnittstelle auf einen ausgeglichenen Baum zugreifen, wird der Baum immer ausgeglichen.

Wir verwenden also eine negative Eigenschaft - dass kein möglicher Client die Abstraktionsgrenze durchbrechen kann - um eine positive abzuleiten - die die Datendarstellungsinvariante immer enthält.

Neel Krishnaswami
quelle

Auf die Daten wird über ein geeignetes Orakel zugegriffen, aber das bedeutet nicht unbedingt, dass es nicht berechenbar ist, direkt darauf zuzugreifen

David Harris,

Datenabstraktion ist im Wesentlichen ein definierbares Ergebnis: Es heißt, dass kein Programm in der Programmiersprache Abstraktionsgrenzen überschreiten kann. Wenn Sie einen außersprachlichen Mechanismus verwenden (z. B. starten Sie Ihren Debugger), können Sie natürlich sehen, welche privaten Felder diese Hash-Tabelle enthält.

Neel Krishnaswami

Kolmogorov Komplexität könnte in diese Kategorie fallen.

Man kann zeigen, dass es bestimmte Saiten gibt, die von keiner Turing-Maschine komprimiert werden können. Diese Zeichenfolgen verhalten sich "generisch", sodass Sie die zufälligen Eigenschaften bestimmter Informationen und Rechenaufgaben untersuchen können, indem Sie das Verhalten in Bezug auf eine (nicht zufällige) inkompressible Zeichenfolge untersuchen.

David Harris
quelle

Vielen Dank, jemand anderes hat dies auch in einer Offline-Diskussion vorgeschlagen. (Ich bin nicht ganz überzeugt, da wir nicht wirklich rechnerisch zufällige Zeichenfolgen verwenden, um Aufgaben der realen Welt auszuführen. Es hat eher einen existenziellen Charakter als etwas zu bauen. Ich sollte wahrscheinlich ein bisschen mehr darüber nachdenken, was ich genau mit einem positiven Ergebnis meine ps: Meine ursprüngliche Motivation war es, Studenten, die die Berechenbarkeitstheorie lernen, ein Beispiel für die Nützlichkeit negativer Ergebnisse beim Aufbau von Dingen zu geben, um Aufgaben der realen Welt auszuführen.)

Kaveh

Während man in der Praxis keine inkompressiblen Strings konstruiert (und nicht konstruieren kann), ist es sehr üblich, einen String zufällig zu konstruieren. Dann wird es mit hoher Wahrscheinlichkeit inkompressibel sein.

David Harris