Funkcje jednokierunkowe w odniesieniu do różnych granic zasobów

Nieformalnie funkcje jednokierunkowe są definiowane w odniesieniu do algorytmów PTIME. Są obliczalne w czasie wielomianowym, ale nie są odwracalne w czasie wielomianowym średniego przypadku. Istnienie takich funkcji jest ważnym otwartym problemem w informatyce teoretycznej.

Interesują mnie funkcje jednokierunkowe (niekoniecznie dla aplikacji kryptograficznych) zdefiniowane w odniesieniu do różnych granic zasobów. Takimi granicami zasobów może być LOGSPACE lub ograniczony niedeterminizm.

Czy istnieje potencjalny (naturalny) problem, który jest jednokierunkowy w odniesieniu do algorytmów LOGSPACE? Czy istnieje potencjalny (naturalny) problem, który jest jednokierunkowy w odniesieniu do niedeterministycznych algorytmów liniowego czasu ( $\text{NTIME(n)}$ )?

Nie przeszkadza mi najgorsza twardość odwracalności w odniesieniu do powyższych ograniczeń zasobów.

cc.complexity-theory one-way-function

— Mohammad Al-Turkistany
źródło

Czy widziałeś eprint.iacr.org/2013/001.pdf ? Temat tego artykułu może, ale nie musi być dokładnie dla ciebie odpowiedni, ale techniki zawarte w artykule (a może nawet cytaty) mogą prowadzić do czegoś pożytecznego.

— Daniel Apon,

Streszczenie nie pomaga, ale dziękuje za twoją pomoc.

— Mohammad Al-Turkistany

No cóż - mam nadzieję, że nowa odpowiedź tak. :)

— Daniel Apon

Tak, robi :)

— Mohammad Al-Turkistany,

$^0$

Dwa konkretne przykłady obejmują:

Mnożenie liczb całkowitych (istnieją pewne subtelności dla standardowej MFW, ale jeśli zależy ci tylko na najgorszym przypadku, wystarczy)

Kandydat Impagliazzo-Naor na podstawie sumy częściowej: . $f(a_1,...,a_n,S) := (a_1,..., a_n, \sum_{i \in S} a_i \mod 2^n)$

— Manu
źródło

Dzięki Emanuele. To odpowiada przypadkowi Logspace. Dla kompletności, czy możesz wymienić niektóre z tych funkcji w swojej odpowiedzi.

— Mohammad Al-Turkistany

Dodałem dwa przykłady.

— Manu

Wielkie dzięki Emanuele. Czy istnieje wgląd, który wyjaśnia trudność odwracania tych funkcji (za pomocą algorytmów LOGSPACE)?

— Mohammad Al-Turkistany