Konsekwencje OWF dla złożoności

Powszechnie wiadomo, że istnienie funkcji jednokierunkowych jest konieczne i wystarczające dla dużej części kryptografii (podpisy cyfrowe, generatory pseudolosowe, szyfrowanie kluczem prywatnym itp.). Moje pytanie brzmi: jakie są teoretyczne konsekwencje istnienia funkcji jednokierunkowych? Na przykład sugerują to OWF $\mathsf{NP}\ne\mathsf{P}$ , $\mathsf{BPP}=\mathsf{P}$ , i $\mathsf{CZK}=\mathsf{IP}$ . Czy istnieją inne znane konsekwencje? W szczególności, czy MFW sugerują, że wielomianowa hierarchia jest nieskończona?

Mam nadzieję, że lepiej zrozumiem związek między najgorszym przypadkiem a średnią twardością. Interesują mnie również wyniki idące w drugą stronę (tj. Wyniki teoretyczne złożoności, które sugerowałyby OWF).

— Tomasz
źródło

Czy sprawdziłeś literaturę o światach Impagliazzo?

— Kaveh

@ MohammadAl-Turkistany tzw

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$ implikuje

P \neq P H

$\mathsf{P} \neq \mathsf{PH}$ . Nie wyklucza to jednak zawalenia: jest nadal zgodne z

N P = P H

$\mathsf{NP} = \mathsf{PH}$ .

— Sasho Nikolov

Thomas, istnieje wiele kryptograficznych dolnych granic dla efektywnego uczenia się PAC. Sądzę, że są o tym wspominani w gazecie Impagliazzo z pięciu światów

— Sasho Nikolov,

Nie sądzę, by istnienie OWF (zgodnie z ich standardową definicją) implikowało

P = B P P

$P=BPP$ . Do takich derandomizacji potrzebujemy generatorów pseudolosowych z rozciągnięciem wykładniczym, a OWF nie są odpowiednie do takich celów.

— Mahdi Cheraghchi,

@MarzioDeBiasi:

P \neq U P

$P \neq UP$ iff OWF istnieją dla OWF typu „złożoności strukturalnej” (iniekcyjne obliczalne funkcje wieloczasowe bez odwrotności wieloczasowej). Rodzaj OWF potrzebnych do szyfrowania, jak w pytaniu, wydaje się nieco silniejszy (wymagający nieodwracalności przez losowych lub nierównomiernych przeciwników na danych wejściowych o średniej wielkości).

— Joshua Grochow

Odpowiedzi:

To spóźniona odpowiedź.

Po pierwsze, aby poprawić to, co napisałeś: pseudolosowość kryptograficzna (ta uzyskana z OWF) nie ma wystarczającej rozciągliwości, aby zdemandalizować „naturalnie zdefiniowane” klasy złożoności obliczeniowej. W starej pracy (z początku lat 80.) Andrew Yao pokazuje pewne subandponencjalne derandomizacje czasu dla RP itp. Przy użyciu tych obiektów (przy okazji, jest to natychmiastowe), ale nie jest znana silniejsza derandomizacja. Zauważ, że pod względem mocy oszukiwania kryptograficzne PRG są silniejsze niż to, czego potrzebujesz do derandomizacji, ale jednocześnie pod względem ich rozciągnięcia są słabsze niż ich typowe teoretyczne analogi złożoności (wynika to z kolejności kwantyfikacji w definicji PRG).

Jak wspomniał Sasho Nikolov, istnieje wiele przykładów uczenia się PAC. Rzuć okiem na bardzo wczesną pracę Kearnsa i Valianta na temat niemożności uczenia się formuł i automatów (śledź w Google Scholar odnośniki stamtąd). Także interpolacja ma konsekwencje w złożoności dowodu - spójrz także we wczesnych pracach Jana Krajicka i Pavla Pudlaka. Nie jestem jednak pewien, czy uważasz, że są to implikacje teoretyczne dotyczące złożoności (ale tak robię).

- Periklis

— użytkownik17164
źródło

Rozkład na czynniki całkowite jest powszechnie uważany za najlepszego kandydata na funkcje jednokierunkowe i znajduje się w TFNP. Na podstawie streszczenia tego artykułu, czy hierarchia wielomianowa upadnie, jeśli funkcje Ont są odwracalne? , daje relatywizowany wynik ujemny poprzez zbudowanie wyroczni, w której funkcje TFNP są wydajnie obliczalne, ale hierarchia czasu wielomianowego jest nieskończona. Jednak wynik nie jest dokładnie tym, czego szukasz.

— Mohammad Al-Turkistany
źródło