Status światów Impagliazzo?

W 1995 r. Russell Impagliazzo zaproponował pięć światów złożoności:

1- Algorytmika: ze wszystkimi niesamowitymi konsekwencjami.$P=NP$

2- Heuristica: problemy kompletne są trudne w najgorszym przypadku ( ), ale można je skutecznie rozwiązać w przeciętnym przypadku.$NP$$P \ne NP$

3- Pessiland: Występują problemy z niepełną średniej wielkości przypadków , ale funkcje jednokierunkowe nie istnieją. Oznacza to, że nie możemy wygenerować trudnych wystąpień problemu z zakończonym znanym rozwiązaniem. $NP$$NP$

4- Minikrypt: istnieją jednokierunkowe funkcje, ale systemy kryptograficzne z kluczem publicznym są niemożliwe

5- Cryptomania: Istnieją systemy kryptograficzne z kluczem publicznym i możliwa jest bezpieczna komunikacja.

Który świat jest faworyzowany przez ostatnie postępy w złożoności obliczeniowej? Jaki jest najlepszy dowód na wybór?

Russell Impagliazzo, Osobiste spojrzenie na złożoność średnich przypadków , 1995

Impagliazzo's Five Worlds, blog The Computational Complexity

Mniej więcej rok temu współorganizowałem warsztaty na temat złożoności i kryptografii: status światów Impagliazzo , a slajdy i filmy na stronie internetowej mogą być interesujące.

Krótka odpowiedź jest taka, że ​​niewiele się zmieniło w tym sensie, że większość badaczy wciąż wierzy, że żyjemy w „Kryptomanii” i wciąż mamy mniej więcej takie same dowody na to, a także niewielki postęp w zawaleniu jednego ze światów dla siebie nawzajem.

Być może najbardziej znaczącą częścią nowych informacji jest algorytm Shora, który pokazuje, że przynajmniej po zamianie P na BQP najczęściej używane kryptosystemy klucza publicznego są niepewne. Jednak ze względu na kryptosystemy oparte na kratach domyślnym założeniem jest to, że nawet w tym przypadku żyjemy w kryptomanii, choć być może konsensus jest nieco słabszy niż w przypadku klasycznym. Nawet w klasycznym przypadku wydaje się, że istnieje o wiele więcej dowodów na istnienie funkcji jednokierunkowych („Minicrypt”) niż na istnienie szyfrowania kluczem publicznym („Cryptomania”). Mimo to, biorąc pod uwagę wysiłek, jaki ludzie włożyli w próbę złamania różnych kryptosystemów klucza publicznego, istnieją również istotne dowody na to drugie.

Dobre pytanie, ale naukowcom nie udało się nawet oddzielić „Algorytmiki” od pozostałych przypadków, nie mówiąc już o określeniu dokładnego świata, w którym żyjemy.

To powiedziawszy, istnieje kilka prac badawczych na ten temat. Patrz na przykład: na temat możliwości oparcia kryptografii na założeniu, że P! = NP Goldreicha i Goldwassera, oraz ich referencje.

Zobacz także O oparciu funkcji jednokierunkowych na twardości NP Adi Akavia i in.

Ponadto dobrze wiadomo, że dekodowanie niektórych kryptosystemów jest trudne dla NP (patrz na przykład kryptosystem McEliece lub kryptografia oparta na sieci ). Nie wiem, dlaczego NIE rozwiązuje to problemu, ponieważ nie znam takich kryptosystemów. Zobacz komentarze Petera Shora poniżej.

Proponuję również rzucić okiem na dyskusję w Stackoverflow . Przegląd literatury, która cytuje prace Impagliazzo, może być również pouczający.

EDYCJA: Interesujące mogą być następujące wyniki:

Feigenbaum i Fortnow. Losowa samoredukowalność kompletnych zestawów. SIAM Journal on Computing, 22: 994–1005, 1993.

Bogdanov i Trevisan. Redukcje od najgorszych do średnich przypadków dla problemów NP. W materiałach z 44. dorocznego sympozjum IEEE na temat podstaw informatyki, strony 308–317, 2003.

Akavia, Goldreich, Goldwasser i Moshkovitz. Na podstawie funkcji jednokierunkowych opartych na twardości NP

Gutfreund i Ta-Shma. Nowe związki między derandomizacją, złożonością najgorszego przypadku i złożonością średniego przypadku. Tech. Rep. TR06-108, Electronic Colloquium on Computational Complexity, 2006.

Bogdanov i Trevisan. Średnia złożoność przypadków. Uznany. Teoria trendów. Comput. Sci. 2, 1 (październik 2006), 1-106. DOI = http://dx.doi.org/10.1561/0400000004