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

20

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 .N.P.P./polyP.H.Σ2)P.Σ2)P.Σ3)P.N.P.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 )?P.H. N.P.ZAvmirzasolmi-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 .ZAvmirzasolmi-P./polyZAvmirzasolmi-P./polyP./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ę.)N.P.-ZAvmirzasolmi-P./poly

MS Dousti
źródło
2
(1) Nie sądzę, aby założenie, że hierarchia wielomianowa się nie zawali, sugeruje, że istnieje trudny problem w NP. Sekcja 18.4 Arory i Baraka stwierdza: „[…] chociaż wiemy, że jeśli P = NP, to wielomianowa hierarchia PH zapada się do P […], nie mamy analogicznego wyniku dla średniej złożoności przypadku.”
Tsuyoshi Ito
3
(2) Czy P / poly w pytaniu jest zwykle najbardziej złożonym przypadkiem, czy rozważasz jego analogiczny przypadek? Jeśli jest to najgorszy przypadek, potrzebujesz zarówno DistP ≠ DistNP, jak i NP⊈P / poly, aby mieć taki problem, a jeśli się utrzymają, to każdy problem z kompletnością DistNP spełnia ten wymóg, ponieważ koniecznie jest problem z kompletnością DistNP NP-complete, jeśli wyrzucimy rozkład wejściowy.
Tsuyoshi Ito
@Tsuyoshi: Wielkie dzięki. Masz rację na temat P / poli w najgorszym przypadku w porównaniu ze średnim przypadkiem. Z drugiej strony (o pierwotnym problemie), myślę, że muszę interpretować P / poly jako klasę średniej wielkości przypadków .
MS Dousti
Przeczytałem wersję 3. Tautologicznie taki problem istnieje tylko wtedy, gdy DistNP ⊈ Average-P / poli. 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 z powodu redukcji (między problemami dystrybucyjnymi). Ale może prosisz o bardziej naturalny problem przy silniejszym założeniu.
Tsuyoshi Ito
@Tsuyoshi: Dziękuję. Czy możesz zamienić komentarze w odpowiedź, abym mógł je zaakceptować?
MS Dousti

Odpowiedzi:

7

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

Tsuyoshi Ito
źródło