Funktion, die garantiert einseitig ist, wenn es Einwegfunktionen gibt?

13

Es gibt einen alten Trick, um einen Algorithmus aufzuschreiben, der, wenn P = NP, SAT in Polynomialzeit löst. Im Wesentlichen listet man alle Polynom-Zeitmaschinen und Multi-Tasks darüber auf.

Gibt es einen analogen Trick für Einwegfunktionen (oder auch Einweg-Falltürfunktionen)? Das heißt, können wir eine Funktion aufschreiben, die, wenn Einwegfunktionen existieren, notwendigerweise eine Einwegfunktion ist?

Es scheint keinen einfachen Weg zu geben, den P = NP-Trick nachzuahmen. In diesem Fall können wir eine Lösung schnell erkennen, wenn wir eine erhalten. Wenn ich jedoch über alle Polynomzeitfunktionen mehrere Aufgaben ausführe, gibt es keine offensichtliche Möglichkeit, eine Einwegfunktion zu erkennen, wenn ich zu einer komme.

Wenn die Antwort auf die obige Frage Nein lautet, gibt es eine Art Argument, warum wir das nicht können? Vielleicht würde das Aufschreiben einer solchen Funktion irgendwie beweisen, dass es Einwegfunktionen gibt?

Timothy Chow
quelle
Hallo Timothy Chow, können Sie vielleicht helfen und auf einen Link verweisen, bei dem der Trick zum Aufschreiben eines Algorithmus, der, wenn P = NP, SAT in Polynomzeit löst, formalisiert ist? Vielen Dank allot
Avi Tal
@AviTal Siehe zum Beispiel: scholarpedia.org/article/Universal_search
Vanessa

Antworten:

11

Ja, eine solche Funktion wurde von Levin selbst gefunden und erst kürzlich veröffentlicht:

Die Geschichte der Einwegfunktionen . Probleme der Informationsübertragung (= Problemy Peredachi Informatsii), 39 (1): 92-103, 2003.

Bjørn Kjos-Hanssen
quelle
Vielen Dank! Mit Google Scholar konnte ich anhand dieser Referenz eine Referenz für ein vollständiges Kryptosystem mit öffentlichem Schlüssel von Grigoriev, Hirsch und Pervyshev, Groups-Complexity-Cryptology 1 (2009), 1-12, finden.
Timothy Chow
Könnten Sie bitte Einzelheiten dieser Funktion erläutern? B. warum es nach n ^ 2 Schritten abbricht, warum 'eine Kopie des Programmpräfixes erhalten und es, sowie die Eingabelänge, auf die Ausgabe zwingen' und was 'nur an Stellen, an denen eine solche mögliche Erweiterung eindeutig ist' genau bedeutet . Ich weiß nicht, ob dies eine gesonderte Frage verdient.
Galmeida
@ BjørnKjos-Hanssen cstheory.stackexchange.com/questions/44496/…
galmeida