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).

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

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.