Problemy w NP, ale nie w średniej-P / poli

Karp-Lipton Theoem , że jeśli , a następnie P H zapada się Ď P 2 . W związku z tym, zakładając, że separację między Ď P 2 i Ď P 3 , nr N P -Complete Problem ten należy do P / P ° l y .$\mathsf{NP} \subset \mathsf{P/poly}$$\mathsf{PH}$$\mathsf{\Sigma^P_2}$$\mathsf{\Sigma^P_2}$$\mathsf{\Sigma^P_3}$$\mathsf{NP}$$\mathsf{P/poly}$

Interesuje mnie następujące pytanie:

Przy założeniu, że nie zapadnie się do realizacji lub dowolny inny rozsądne założenie złożoności strukturalnej, co mocno na średnią N P problemy okazały się nie leżą w A v e r o g e - P / P ° l Y (jeśli )?$\mathsf{PH}$ $\mathsf{NP}$$\mathsf{Average\mbox{-}P/poly}$

Definicję można znaleźć w Relacjach między złożonością przypadku średniego a złożonością najgorszego przypadku . Dzięki Tsuyoshi za zwrócenie uwagi, że faktycznie muszę użyć A v e r a g e - P / p o l y zamiast P / p o l y .$\mathsf{Average\mbox{-}P/poly}$$\mathsf{Average\mbox{-}P/poly}$$\mathsf{P/poly}$

Wydaje mi się, że istnieją problemy, takie jak (wersje decyzyjne) FACTORING lub DLOG, które przypuszcza się, że leżą w , ale przypuszczenie to nie zostało udowodnione na podstawie separacji między klasy złożoności. (Proszę popraw mnie jeżeli się mylę.)$\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$

To nieco ulepszona wersja moich dwóch komentarzy do pytania w połączeniu.

Dla uproszczenia ograniczmy naszą uwagę do problemów dystrybucyjnych w DistNP (aka (NP, P-obliczalny)). Następnie szukasz problemu w DistNP ∖ Average-P / poly. Tautologicznie taki problem istnieje tylko wtedy, gdy DistNP ⊈ Average-P / poly. A jeśli DistNP ⊈ Średnia-P / poli, to każdy problem kompletny dla DistNP leży poza średnią-P / poli, ponieważ średnia-P / poli jest zamknięta przy zmniejszeniu średniej liczby przypadków.

(Biorąc pod uwagę większą klasę SampNP (alias (NP, P-samplable) ) zamiast DistNP niewiele zmienia sytuację, ponieważ DistNP ⊆ Średnia-P / poli wtedy i tylko wtedy, gdy SampNP ⊆ Średnia-P / poli. Ta równoważność jest bezpośrednia następstwo wyniku Impagliazzo i Levina [IL90], że każdy problem dystrybucyjny w SampNP jest przypadkiem średnim przypadkiem redukowanym do pewnego problemu dystrybucyjnego w DistNP.)

Nie wiem, które naturalne założenie implikuje DistNP ⊈ Średnia-P / poli. Założenie, że hierarchia wielomianowa się nie załamuje, nie oznacza nawet słabszej konsekwencji, że DistNP ⊈ Średnia-P, zgodnie z rozdziałem 18.4 Arory i Baraka [AB09]: „[…], chociaż wiemy, że jeśli P = NP , a następnie hierarchia wielomianowa PH zapada się do P […], nie mamy analogicznego wyniku dla średniej złożoności przypadku. ”

Bibliografia

[AB09] Sanjeev Arora i Boaz Barak. Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press, 2009.

[IL90] Russell Impagliazzo i Leonid A. Levin. Nie ma lepszych sposobów na generowanie twardych instancji NP niż jednolite losowe wybieranie. W 31 Annual Symposium on Podstaw Informatyki , 812-821, październik 1990. http://dx.doi.org/10.1109/FSCS.1990.89604