Argumenty za istnieniem funkcji jednokierunkowych

Czytałem w kilku artykułach, że powszechnie uważa się istnienie funkcji jednokierunkowych . Czy ktoś może wyjaśnić, dlaczego tak jest? Jakie mamy argumenty za poparciem istnienia funkcji jednokierunkowych?

Oto argument, że funkcje jednokierunkowe powinny być trudne do odwrócenia. Załóżmy, że istnieje trudna do rozwiązania klasa problemów 3-SAT z posadzonymi rozwiązaniami. Rozważ następującą mapę:

gdzie oznacza dowolny ciąg bitów, r jest ciągiem bitów (można z nich korzystać do materiału siewnego generator liczb losowych, lub można poprosić o tak wielu przypadkowych kawałków, jak trzeba) i s jest k -sat problemem konieczności X jak posadzone rozwiązanie, w którym generator liczb losowych określa dokładnie, jaki problem k- SAT wybierzesz. Aby odwrócić tę funkcję jednokierunkową, musisz rozwiązać problem k- SAT za pomocą posadzonego rozwiązania.$x$$r$$s$$k$$x$$k$$k$

Argument ten pokazuje, że odwrócenie funkcji jednokierunkowej jest tak trudne, jak rozwiązywanie problemów SAT za pomocą posadzonych rozwiązań. A ponieważ k- SAT jest problemem NP-zupełnym, jeśli możesz dowiedzieć się, jak konstruować twarde instancje z posadzonymi rozwiązaniami dla dowolnego problemu NP, możesz sadzić rozwiązania we wzorach k -SAT.$k$$k$$k$

Nie zostało udowodnione, że można znaleźć klasę problemów z NP-zupełnymi rozwiązaniami, które są tak samo trudne jak arbitralne problemy z NP-zupełnymi (a nawet jeśli jest to prawdą, będzie to niezwykle trudne do udowodnienia) , ale ludzie zdecydowanie wiedzą, jak sadzić rozwiązania problemów SAT w sposób, którego nikt obecnie nie umie rozwiązać.$k$

DODANO: Teraz zdaję sobie sprawę, że połączenie to zostało już podane (bardziej szczegółowo) w Abadi, Allender, Broder, Feigenbaum i Hemachandra ; zwracają uwagę, że funkcje jednokierunkowe mogą dawać rozwiązane trudne przypadki SAT i odwrotnie.

Mówiąc w bardziej nieformalnym języku, brak jednokierunkowych funkcji pokazuje, że naprawdę trudne zagadki nie mogą istnieć. Jeśli istnieje rodzaj łamigłówki, w którym ktoś może wymyślić zarówno układankę, jak i jej rozwiązanie algorytmicznie, istnieje również algorytm wielomianowy do znalezienia rozwiązania układanki. Wydaje mi się to bardzo sprzeczne z intuicją. Oczywiście może istnieć wielomianowa luka; może się zdarzyć, że jeśli stworzenie układanki wykona kroków, to rozwiązanie może zająć O ( n 3 ) kroków. Jednak moja intuicja mówi, że powinna istnieć luka wielobiegunowa. $n$$O(n^3)$

Dam krótką odpowiedź: istnienie pozornie trudnych problemów, takich jak FACTORING lub DISCRETE LOG, sprawiło, że teoretycy wierzą, że OWF istnieje. W szczególności przez dziesięciolecia (od lat 70.) próbowali znaleźć wydajne algorytmy (probabilistyczny czas wielomianowy) dla takich problemów, ale żadna próba się nie powiodła. To rozumowanie jest bardzo podobne do tego, dlaczego większość badaczy uważa, że ​​P ≠ NP.

Argument Sasho opiera się na odwiecznym problemie P = NP, dla którego obecnie nie ma konsensusu.

$r_1,r_2,r_3,\ldots,r_n$$s_1,s_2,s_3,\ldots,s_n$

$f(r_i,s_i) = r_i \oplus s_i = c_i$

$f^{-1}(r_i,s_i)$

Możemy naśladować wynik Shannona dla funkcji jednokierunkowych.

$f:\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}$$f:\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$

Problem polega na tym, że nie wiemy, czy istnieją naprawdę losowe liczby, ponieważ pytanie to odpowiada komentarzowi Einsteina na temat „Bóg nie gra w kości”.

Jednak do wszystkich celów generator liczb losowych oparty na fizycznym procesie jest uważany przez ekspertów za wystarczająco losowy.

$(c_i,r_i)$

$f(r_i,s_k)\neq f(r_j,s_k)$$s_k$$f(r_i,s_i) = f(r_j,s_j)$

Czy byłoby to tak proste, jak sugerowanie na przykład funkcji Sinus?

Ponieważ dla danego wejścia i wyjścia sygnał wejściowy można zwiększyć lub zmniejszyć o 360 stopni (lub 2 pi, jeśli jesteś w radianach), to wiele do jednego, więc nigdy nie możesz być pewien, który sygnał miałeś?

Powiedz mi jednak, czy źle zrozumiałem pytanie.