Przytulne dzielnice „P” i „NP-hard”

Niech będzie zadaniem algorytmicznym. (Może to być problem decyzyjny, problem optymalizacji lub inne zadanie.) Nazwijmy X „po stronie wielomianowej”, jeśli wiadomo, że założenie, że X jest trudne NP, oznacza, że ​​załamuje się wielomianowa hierarchia. Nazwijmy X „po stronie NP”, jeśli wiadomo, że X przyjmuje algorytm wielomianowy, który implikuje załamanie się hierarchii wielomianowej.$X$$X$$X$$X$$X$

Oczywiście każdy problem w P występuje po stronie wielomianowej, a każdy problem, który jest NP-trudny, występuje po stronie NP. Również, na przykład, faktoring (lub cokolwiek w skrzyżowaniu NP coNP) jest po stronie wielomianowej. Wykres izomorfizm występuje po stronie wielomianowej. QUANTUM-SAMPLING znajduje się po stronie NP.

1) Interesuje mnie więcej przykładów (jak najbardziej naturalnych) zadań algoritmicznych po stronie wielomianowej i (szczególnie) więcej przykładów po stronie NP.

2) Naiwnie wygląda na to, że strona NP jest rodzajem „sąsiedztwa” problemów trudnych dla NP, a strona P to „sąsiedztwo P”. Czy poprawne jest postrzeganie problemów po stronie NP jako „znacznie trudniejszych” w porównaniu do problemów po stronie P. Lub nawet uznać problemy po stronie NP za „moralnie trudne NP”?

3) (Może to być oczywiste, ale nie widzę tego) Czy jest po obu stronach lub czy istnieją teoretyczne powody, by sądzić, że taki X jest mało prawdopodobny. Aktualizacja Odpowiedź brzmi TAK; patrz odpowiedź Yuvala Filmusa poniżej.$X$$X$

(Jeśli te „strony” są powiązane z rzeczywistymi klasami złożoności i jeśli brakuje mi odpowiedniego żargonu CC lub odpowiednich wyników, proszę dać mi znać.)

Aktualizacja:Istnieje już kilka bardzo dobrych odpowiedzi na to pytanie. Jak zauważył najpierw Yuval Filmus i wspomniał ponownie, pytanie to nie jest formalne i konieczne jest pewne ograniczenie argumentu wskazującego, że X jest po stronie P / NP. (W przeciwnym razie możesz mieć X za zadanie przedstawienia dowodu na 0 = 1, który jest po obu stronach.) Odkładając to na bok, może się zdarzyć, że problemy X (naprawdę) po stronie NP uchwycą w jakiś sposób twardość SAT, chociaż może tak być również w przypadku niektórych problemów po stronie P, w których twardość SAT jest osłabiona (nawet nieznacznie) w możliwy do udowodnienia sposób. Yuval Filmus podał osłabioną wersję SAT, która jest po obu stronach. Andy Drucker podał (w dwóch odpowiedziach) pięć interesujących przykładów, w tym odniesienie do niskiej i wysokiej hierarchii Schöninga, a Scott Aaronson podał dalsze interesujące przykłady, wspomniał o odwróceniu funkcji jednokierunkowej, która jest bliska uchwycenia twardości NP, a jednak po stronie P., a jego odpowiedź omawia również interesujący przypadek QUANTUMSAMPLING. Wspomniałem o starym wyniku tego rodzaju autorstwa Feige i Lund.

Same terminy „po stronie P” i „po stronie NP” oraz oczywiście tytuł pytania zachęcają nas do wyobrażenia sobie „przytulnej dzielnicy” otaczającej P i kolejnej „przytulnej dzielnicy” otaczającej trudne problemy związane z NP. Chciałbym jednak argumentować, że te dwie dzielnice wcale nie są tak „przytulne”!

Jako pierwsze spostrzeżenie, istnieją problemy „po stronie P”, które wydają się „moralnie” znacznie bliższe NP-trudnemu niż P. Jeden przykład, przewidywany przez Gil, oczywiście, jest ogólnym problemem odwracania funkcji jednokierunkowych ( w zależności od dokładnie dozwolonego rodzaju redukcji; patrz Bogdanov-Trevisan lub Akavia i in.).

I odwrotnie, istnieją również problemy „po stronie NP”, które wydają się „arbitralnie dalekie od bycia trudnym do NP. Jednym głupim przykładem jest język losowy L, z prawdopodobieństwem 1 ponad L! Bo jeśli takie L jest w P, to 0 = 1, a matematyka jest niespójna, a zatem PH również się załamuje. ;-RE

(Zauważ, że losowy język L jest również „po stronie P”, z prawdopodobieństwem 1 ponad L. Dla prawie wszystkich takich L ma właściwość, że jeśli są NP-twarde, wówczas NP⊆BPP i PH załamują się. I to daje dowód, znacznie prostszy niż odwołanie się do twierdzenia Ladnera, że ​​istnieją języki po obu „stronach”. Rzeczywiście, pokazuje to, że z niezliczonej nieskończoności języków, „prawie wszystkie” - w rzeczywistości 100% - są po obu stronach!)

To brzmi jak gra młodocianych, ale chciałbym wyciągnąć z tego poważną naukę. Twierdziłbym, że chociaż QUANTUM SAMPLING jest formalnie „po stronie NP”, problem ten jest prawie bliżej bycia „moralnie trudnym do NP” niż przypadkowy język L. Arkhipov i ja (i niezależnie, Bremner-Jozsa-Shepherd) wykazali, że jeśli QUANTUM SAMPLING znajduje się w P (a raczej w SampBPP, klasie problemów rozwiązywania prób wielomianowych), to P ^#P = BPP ^NP , a zatem załamuje się hierarchia wielomianowa. Jednak jeśli jesteś maszyną BPP, wyrocznia dla BosonSampling, o ile nam wiadomo, nie przybliży cię do rozwiązania problemów związanych z całkowitą NP, niż przypadkowa wyrocznia. Tylko jeśli masz już zdolność rozwiązywania problemów z NP-zupełnym - powiedzmy,Maszyna ^NP - czy „zauważasz”, że wyrocznia BosonSampling jeszcze bardziej zwiększa twoje możliwości, do #P. Ale właściwość zwiększania NP do #P wydaje się inna niż, a może nawet „ortogonalna”, własność bycia NP trudnym we własnym zakresie.

Nawiasem mówiąc, cudownym otwartym problemem sugerowanym przez pytanie Gila jest to, czy BosonSampling jest również „po stronie P.”. To znaczy, czy możemy pokazać, że jeśli NP zredukuje się do BosonSampling, wówczas PH załamie się? Choć może brakuje mi czegoś oczywistego, na pierwszy rzut oka nie mam pojęcia, jak udowodnić taką rzecz, bardziej niż wiem, jak udowodnić silniejszą implikację, że jeśli NP ⊆ BQP to PH załamie się.

Dwa komentarze, z których żaden nie stanowi odpowiedzi, ale może dostarczyć użytecznych dalszych informacji.

$\cap$$\cap$

http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Abstracts/low.ps.abstr_html

$t$

http://eccc.hpi-web.de/report/1999/045/

Żeby było jasne, nie ma prawdziwych dowodów na to, że ten problem nie jest trudny do NP lub że jest łatwy w jakimkolwiek sensie. Wygląda jednak zupełnie inaczej niż inne trudne problemy w NP. Myślę, że jest to jeden z najciekawszych kandydatów na problemy pośrednie NP, a nie taki, który jest dobrze znany.

$X$

$M_i$$M_i$$n^{\log\log i}$$(\alpha,\beta)$

$f(n)$$f(1) = 1$$f(n)$$f(n+1)$$X_n$$(\phi,1^{|\phi|^{f(|\phi|)}})$$|\phi| \leq n$$\phi$$x$$\log n$$x \in L(M_{f(n)}) \triangle X_n$$f(n+1) = f(n)+1$$f(n+1) = f(n)$$f(n)$$n$

$X$$(\phi,1^{|\phi|^{f(|\phi|)}})$$\phi$$X = \bigcup_n X_n$

$X$$M_i$$f(n) \leq i$$n$$M_i$

$g$$X$$n^k$$X$$f(n) \longrightarrow \infty$$f(n) > k$$n \geq n_0$$g$$n_0$$(\phi,1^{|\phi|^{f(|\phi|)}})$$f$$g$

$PH$$P \neq NP$

$SAT$$NP$$SAT$$P = NP$

http://people.cs.uchicago.edu/~fortnow/papers/2q.pdf

$SAT$$\psi$$m$$n \ll m$$\psi$$n$$m$$SAT$

W odpowiedzi na pytanie Bodlaender, Downey, Fellows i Hermelin Fortnow i Santhanam wykazali, że taka redukcja kompresji jest mało prawdopodobna, ponieważ doprowadziłaby do upadku Poly Hierarchy:

http://people.cs.uchicago.edu/~fortnow/papers/compress.pdf

Ich wynik zastosowano do losowych redukcji pozwalających na jednostronny błąd. Udowodniłem odpowiedni wynik dla błędu dwustronnego w

http://eccc.hpi-web.de/report/2012/112/

(Każdy z tych dokumentów faktycznie zawiera silniejsze i bardziej szczegółowe informacje niż wyniki cytowane powyżej).

$PH$$PPAD$$PH$$A$$PPAD^A$$TFNP^A$$PH^A$

http://people.cs.uchicago.edu/~fortnow/papers/phq.pdf

$X$$P$ $\Rightarrow$ $PH$$PH$

Przekonałem się do tego wyniku Feige i Lund, który pokazuje, że dopóki hierarchia wielomianowa się nie załamie, trudno jest odgadnąć nawet bardzo częściowe informacje na temat stałej macierzy losowej.

Uriel Feige i Carsten Lund, O twardości obliczania stałej stałych losowych. Złożoność obliczeniowa 6 (1996/1997) 101-132.

Chciałbym również wspomnieć o dwóch dodatkowych istotnych wynikach, na które zwróciłem uwagę Uri Feige:

Poniższe dwa artykuły stosują to w kontekście kernelizacji (algorytmy ustalone parametrycznie).

Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: O problemach bez jąder wielomianowych. J. Comput. Syst. Sci. 75 (8): 423–434 (2009)

Lance Fortnow, Rahul Santhanam: Nieskuteczność kompresji instancji i zwięzłe PCP dla NP. J. Comput. Syst. Sci. 77 (1): 91–106 (2011 r.)