Algorithmus zum Invertieren einer bijektiven Funktion.

8

Gibt es einen verallgemeinerten Algorithmus zum Finden der Umkehrfunktion einer beliebigen bijektiven Funktion?

  • Damit dieser Algorithmus nützlich ist, muss er eventuell angehalten werden, sobald die richtige Antwort gefunden wurde.
  • Abgesehen von der Anforderung, dass die Lösung irgendwann gefunden werden muss, gibt es keine zeitlichen Einschränkungen hinsichtlich der Zeit, die zum Auffinden oder Ausführen der inversen Funktion benötigt wird (in diesem Sinne wäre etwas Besseres als Bruteforce-Guess-and-Check interessanter).

Wenn beispielsweise ein solcher verallgemeinerter Algorithmus existiert, könnte er nach einem Dekomprimierungsalgorithmus für einen verlustfreien Komprimierungsalgorithmus suchen.

BEARBEITEN:

Ich mochte die Annahmen von Evgenij Thorstensen sehr, da sie meine Frage ziemlich gut zusammenfassten.

Annahmen

  • Berechenbare bijektive Funktionen über ein festes Alphabet (sagen wir {0, 1})
  • Dargestellt durch eine deterministische Turing-Maschine (DTM), die sie berechnet
  • Der vorgeschlagene Algorithmus könnte nach einem DTM suchen, der die ursprüngliche Ausgabe der bijektiven Funktion invertiert.

Ein weiterer Versuch, es zu erklären:

Gegeben: Bijektive Funktion F, die X von Domäne A auf Y von Domäne B abbildet.

Der vorgeschlagene Algorithmus sollte in der Lage sein, nach einer Bijektivfunktion zu suchen G, die Y von Domäne B auf X von Domäne A abbildet, so dass G(F(X))=Xund F * G = Iwo Isich die Identitätsfunktion befindet.

ds.algorithms Kendall Hopkins
quelle
In welcher Form wird der Algorithmus eingegeben?
Lev Reyzin
Wie könnte die Form der Eingabe die Existenz einer Lösung verändern?
Kendall Hopkins
1
Es wird angenommen, dass Einwegpermutationen existieren (z. B. RSA). Ich nehme an, Sie suchen nach negativen Ergebnissen?
Arnab
2
Als Randnotiz, wenn Sie abstimmen wollen, wäre es hilfreich zu erklären, warum
Suresh Venkat
2
Ich habe gerade abgestimmt, weil diese Frage nicht ausreichend spezifiziert ist, um eine konkrete Antwort zu geben. Zu vage. Zur Verbesserung: Was ist die genaue Eingabe in den Algorithmus und was ist die genaue Ausgabe des Algorithmus? Ansonsten raten wir nur, was Sie meinen könnten.
Aaron Sterling

Antworten:

7

Es gab Artikel über die automatische Umwandlung von Algorithmen für bijektive Funktionen in Algorithmen für die inverse Funktion; Mein erstes eigenes Konferenzpapier war eines davon. Die Klasse der Algorithmen, die auf diese Weise invertiert werden können, ist jedoch stark eingeschränkt, wie die anderen Antworten bereits nahe legen.

David Eppstein
quelle
4

In einer völlig unstrukturierten Domäne ist das Beste, was Sie tun können, die Brute-Force-Suche, deren Zeit in der Größe der Domäne linear ist. Wenn es sich bei der Domäne jedoch um n-Bit-Zeichenfolgen handelt, ist dies in n exponentiell.

(Beachten Sie, dass bei einem effizienten Wechselrichter mit vollständig allgemeinen Funktionen durch Invertieren der Ganzzahlmultiplikationsfunktion ein effizienter Faktorisierungsalgorithmus erhalten wird.)

Joshua Grochow
quelle
Es müsste nicht effizient sein. Nur weil ein Algorithmus zum Invertieren einer bestimmten bijektiven Funktion nichts über die Umkehrung dieser Funktion aussagt. Zum Beispiel Komprimierung / Dekomprimierung.
Kendall Hopkins
Ich denke auch, dass Sie Probleme mit dem Stopp-Problem haben könnten, wenn Sie einfach eine Lösung brutal erzwingen würden. Da müsste jeder Versuch auf Richtigkeit überprüft werden (Run). Was ist, wenn einer der Brute-Force-Versuche eine Endlosschleife versucht? Was ist, wenn die Ausführung der Lösung unendlich lange dauert?
Kendall Hopkins
Sie können die Verzahnung verwenden, um das Problem der Endlosschleife zu vermeiden. en.wikipedia.org/wiki/Dovetailing_%28computer_science%29
Aaron Sterling
@ Aaron Sehr interessante Lösung für die Endlosschleife. Ich glaube, es löst das Problem immer noch nicht, wenn die Ausführung der richtigen Lösung unendlich lange dauern würde (obwohl die Nützlichkeit einer solchen Lösung fraglich ist).
Kendall Hopkins
1
Die ganzzahlige Multiplikation ist nicht bijektiv, daher ist Ihre Notiz hier offtopisch.
Alexandru
3

Wie @arnab in den Kommentaren hervorhob, sind Einwegpermutationen ein kryptografisches Grundelement. Wenn Sie beliebige Funktionen effizient invertieren möchten, müssen Sie (zusätzlich zum Factoring) kryptografische Barrieren überwinden.

Lev Reyzin
quelle
Ich bin mir ziemlich sicher, dass eine "verallgemeinerte" kryptografische Funktion nicht bijektiv ist, da Sie bei Verwendung verschiedener Schlüssel / Daten möglicherweise dieselben Daten erhalten (unwahrscheinlich, aber immer noch möglich). Wenn Sie eine kryptografische Funktion mit einem voreingestellten Schlüssel angegeben hätten, müsste der verallgemeinerte Algorithmus nur nach einem Algorithmus suchen, der den privaten Schlüssel bruteforce (unter Berücksichtigung der Öffentlichkeit), er müsste sich selbst nicht bruteforce.
Kendall Hopkins
RE "Der verallgemeinerte Algorithmus müsste nur nach einem Algorithmus suchen, der den privaten Schlüssel brutal erzwingen könnte" - ich bin nicht sicher, ob ich Sie verstehe. Abgesehen davon, wie kann Brute einen Schlüssel effizient erzwingen?
Lev Reyzin
Die Frage ist nur nach einem Algorithmus zu fragen, der einen Algorithmus zur Lösung des Problems findet, er muss ihn nicht lösen, und die invertierende Lösung oder die invertierende Suchlösung haben JEDE zeitliche Beschränkung.
Kendall Hopkins
3

Wie viele auf dieser Seite bereits darauf hingewiesen haben, könnte die Lösung im Allgemeinen unlösbar sein.

Wenn Sie an invertierbarer Programmierung interessiert sind, ist nicht alles verloren. Eine Alternative zum Finden der Inversen für eine bestimmte Funktion besteht darin, Ihre Funktion aus der Zusammensetzung invertierbarer Funktionen zu konstruieren. In diesem Fall ist das Finden der Inversen trivial.

Ein Beispiel für diesen Ansatz (unter Verwendung von Haskell) wird in diesem Dokument erläutert: http://www.cs.ru.nl/A.vanWeelden/bi-arrows/

Zufällig habe ich Biarrows verwendet, um nur eine Richtung eines Komprimierungsalgorithmus zu schreiben und die andere (Dekomprimierung) kostenlos zu erhalten (kostenlos ist möglicherweise das falsche Wort, die Verwendung ist schwierig, da keine Sprachunterstützung vorhanden ist). .

Jonathan Fischoff
quelle
2

Hier ist ein handgewellter Algorithmus unter einigen starken Annahmen.

Annahmen

  • Berechenbare bijektive Funktionen über ein festes Alphabet (sagen wir {0, 1})
  • Dargestellt durch eine deterministische Turing-Maschine (DTM), die sie berechnet und nicht etwas "mehr" (siehe unten)
  • Wenn der Eingabe-DTM keine bijektive Funktion berechnet, ist es uns egal, was passiert

Mit diesen Annahmen können wir den Eingabe-DTM betrachten und alle Übergänge invertieren (Haltezustände werden zu Startzuständen, Lesen wird zu Schreiben und umgekehrt, wir lesen vom Ende, links ist rechts usw.). Da das TM deterministisch ist und die berechnete Funktion bijektiv ist, ist das Ergebnis auch ein TM und berechnet das Inverse.

Beachten Sie, dass dies beim Factoring nicht funktioniert, da die Multiplikation nicht bijektiv ist. Die Multiplikation von Primzahlen ist , wenn wir die Reihenfolge nicht berücksichtigen, aber ein TM, das Zahlen multipliziert, nicht "nur" die gewünschte bijektive Funktion berechnet, sondern "zu viel", daher meine zweite Annahme (ja, es ist ziemlich stark). Dies passt gut zu den Kommentaren zur Repräsentation.

Evgenij Thorstensen
quelle
Ich bin mir nicht sicher, ob Sie einen DTM anhand der von Ihnen angegebenen Beschreibung "invertieren". Das würde für eine normale Grammatik funktionieren, aber nicht für eine DTM.
Kendall Hopkins
Dies sollte außerdem in der Größe der Eingabe linear sein. Ah, wie nützlich diese starken Annahmen sind. Warum wird es Ihrer Meinung nach für eine DTM nicht funktionieren?
Evgenij Thorstensen
Eine Drehmaschine kann nicht rückwärts laufen (was ich denke, dass Sie darum bitten). Wenn Sie sich in einem Zustand, Symbol und an einer Position befinden, wissen Sie nicht, durch welches Ereignis Sie dorthin gelangt sind (da Sie mehr als in eine Richtung an derselben Position / demselben Zustand / Symbol landen können).
Kendall Hopkins
Ein beliebiger DTM kann das nicht, aber ich habe versucht, die Annahme zu verwenden, dass er eine bijektive Funktion berechnet (tatsächlich darstellt). Wenn wir uns in einem Zustand, Symbol und einer Position befinden, von allen Pfaden, die hierher führen, hätte nur einer schreiben können, was wir jetzt lesen (da es sich um Inversen handelt), andernfalls handelt es sich nicht um eine Darstellung einer bijektiven Funktion. Ich denke, meine Annahme über die Bijektivität ist genau, dass es einen einzigartigen Weg gibt.
Evgenij Thorstensen
Ich bin mir ziemlich sicher, dass das falsch ist. Denken Sie an das hier angegebene Beispiel für die Verschlüsselung (mit einem voreingestellten Pub-Schlüssel). Es ist eine bijektive Funktion, aber Sie können mit einem Verschlüsselungsalgorithmus nicht einfach rückwärts "gehen" (irgendwie der Punkt). Was mich zu dem Schluss bringt, dass Sie für eine bijektive DTM nicht dasselbe tun können.
Kendall Hopkins