Istnieje stara sztuczka polegająca na spisaniu algorytmu, który, jeśli P = NP, rozwiązuje SAT w czasie wielomianowym. Zasadniczo, wymieniono wszystkie wielomianowe wehikuły czasu i wielozadaniowość nad nimi.
Czy istnieje analogiczna sztuczka dla funkcji jednokierunkowych (a nawet jednokierunkowych funkcji zapadni)? Czy możemy zapisać funkcję, która, jeśli istnieją funkcje jednokierunkowe, jest koniecznie funkcją jednokierunkową?
Wydaje się, że nie ma łatwego sposobu naśladowania sztuczki P = NP. W takim przypadku możemy szybko rozpoznać rozwiązanie, gdy je otrzymamy. Ale jeśli wykonuję wielozadaniowość we wszystkich funkcjach czasu wielomianowego, nie ma oczywistego sposobu na rozpoznanie funkcji jednokierunkowej, kiedy do niej dojdę.
Jeśli odpowiedź na powyższe pytanie brzmi „nie”, czy istnieje jakiś argument, dlaczego nie możemy tego zrobić? Może zapisanie takiej funkcji w jakiś sposób udowodniłoby, że istnieją funkcje jednokierunkowe?
źródło
Odpowiedzi:
Tak, taką funkcję odkrył sam Levin, opublikowany nieco później:
Historia funkcji jednokierunkowych . Problemy z przesyłaniem informacji (= Problemy Peredachi Informatsii), 39 (1): 92-103, 2003.
źródło