Czy są jakieś klasy funkcji, które wymagają obliczalnie różnych zasobów do obliczenia w porównaniu do obliczenia ich odwrotności?

Przepraszamy z góry, jeśli to pytanie jest zbyt proste.

Zasadniczo chcę wiedzieć, czy są jakieś funkcje o następujących właściwościach:$f(x)$

Weź na gdy domena i domena kodowa są ograniczone do ciągów bitowych. Następnie$f_n(x)$$f(x)$$n$

1. $f_n(x)$ jest iniekcyjny
2. $f_n(x)$ jest przejmujący
3. $f_n(x)$ zajmuje znacznie mniej zasobów (albo przestrzeń / czas / głębokość obwodu / liczba bramek), aby obliczyć w jakimś rozsądnym modelu niż , gdzie .$f^{-1}_n(y)$$y=f_n(x)$
4. Różnica zasobów dla $f_n(x)$ vs $f^{-1}(y)$ skaluje się jako ściśle zwiększająca się funkcja $n$ .

Potrafię wymyślić przykłady, w których funkcja jest albo hipotetyczna, albo iniekcyjna, ale nie oba, chyba że skorzystam z wymyślonego modelu obliczeniowego. Jeśli wybiorę model obliczeniowy, który pozwala na przesunięcia w lewo w czasie jednostkowym na niektórych pierścieniach, ale nie na przesunięcia w prawo, wówczas oczywiście można wymyślić liniowy nad głową (lub wyższy, jeśli rozważasz bardziej skomplikowaną permutację jako prymityw) . Z tego powodu interesują mnie tylko rozsądne modele, przez które rozumiem głównie maszyny Turinga, obwody NAND lub podobne.

Oczywiście musi to być prawda, jeśli $P\neq NP$ , ale wydaje się, że jest to również możliwe, jeśli $P=NP$ , a zatem nie powinno sprowadzać się do rozstrzygnięcia tego pytania.

Jest całkiem możliwe, że na to pytanie ma oczywistą odpowiedź lub oczywistą przeszkodę w odpowiedzi, której mi brakowało.

Poproszono mnie o ponowne opublikowanie mojego komentarza. Zwróciłem uwagę na ten artykuł Hastada, który pokazuje, że w istnieją permutacje, które są trudne do odwrócenia P:$NC^0$

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)

Dla obwodów boolowskich w oparciu o pełną bazę binarną (przy czym miarą złożoności jest liczba bramek w obwodzie minimalnym) najlepiej znany stosunek dla permutacji C ( f - 1$C(f)$. O ile mi wiadomo, najlepszą stałą uzyskano wtej pracyHiltgen i wynosi ona 2.$\frac{C(f^{-1})}{C(f)} = const$

Edytować. Ponieważ chcesz, aby współczynnik wzrastał, gdy rośnie, nie odpowiada to na twoje pytanie. Jednak w przypadku obwodów boolowskich na pełnej podstawie binarnej nic lepszego nie jest znane.$n$

Przede wszystkim chciałem zauważyć, że surowość nie jest dobrze zdefiniowana bez uprzedniego zdefiniowania kodomainy funkcji. Tak więc w moim poniższym opisie będę wyraźnie odwoływał się do domeny kodowej, nad którą funkcja ma charakter przypuszczający.

Zarówno logarytm dyskretny, jak i funkcje RSA są permutacjami, które przypuszczalnie są trudne do odwrócenia. Poniżej opiszę funkcję dyskretnego logarytmu.

Niech będzie liczbą n- bitową, a g będzie generatorem multiplikatywnej grupy Z ∗ p n . Zdefiniuj f n : Z p n → Z p n jako f n ( x ) = g $p_n$$n$$g$$\mathbb{Z}_{p_n}^*$$f_n \colon \mathbb{Z}_{p_n} \to \mathbb{Z}_{p_n}$ .$f_n(x) = g^x \pmod{p_n}$

$f_n$$\mathbb{Z}_{p_n}$$f_n$