Techniki pokazujące, że problemem jest twardość „otchłani”

36

Biorąc pod uwagę nowy problem w którego prawdziwa złożoność jest gdzieś pomiędzy P a ukończeniem NP, istnieją dwie metody, o których wiem, że mogą być wykorzystane do udowodnienia, że ​​rozwiązanie tego jest trudne:N.P.P.

  1. Pokaż, że problem dotyczy GI (GI = Graph Isomorphism)
  2. Pokazują, że problem w . Według znanych wyników taki wynik sugeruje, że jeśli problem jest NP-zupełny, wówczas PH spada do drugiego poziomu. Na przykład słynny protokół dla Graph Nonisomorphism robi dokładnie to.doo-ZAM.

Czy zastosowano jakieś inne metody (być może o różnych „mocach wiary”)? W przypadku każdej odpowiedzi wymagany jest przykład tego, gdzie rzeczywiście został wykorzystany: oczywiście istnieje wiele sposobów, w jakie można by to pokazać, ale przykłady sprawiają, że argument jest bardziej przekonujący.

Suresh Venkat
źródło
12
Jeśli problem wydaje się wystarczająco trudny, ale nie jesteś w stanie udowodnić, że jest to NPC, szybkie sprawdzenie polega na policzeniu liczby ciągów długości n w języku: jeśli zestaw jest rzadki, prawdopodobnie nie będzie NPC (w przeciwnym razie P = NP według twierdzenia Mahaneya) ... więc lepiej skierować wysiłki na udowodnienie, że jest w P :-) :-) Przykład z bloga Fortnow & Gasarch : {(n, k): istnieje sposób na podzielenie { 1, ..., n} do co najwyżej k pól, aby żadne pole nie miało x, y, z dla x + y = z}
Marzio De Biasi
5
@MarzioDeBiasi brzmi dla mnie jak odpowiedź.
Sasho Nikolov
2
Taka demonstracja składa się z dwóch części: pokazujących trudność umieszczenia problemu w BPP i pokazującą trudność umieszczenia problemu w klasie NP-complete. (Przypomnijmy, że kompletność oznaczenia geograficznego oznacza po prostu „jest w oznaczeniu geograficznym i jest trudna do określenia”).
1
+1 dla Ricky Demer; możemy chcieć mieć listę metod dla pierwszej części.
Pteromys
2
W przypadku problemów w FNP bez oczywistych wersji decyzji w NP, PPAD jest użyteczną (i rosnącą) klasą do rozważenia. Problemy z kompletnym PPAD obejmują wiele problemów związanych ze znajdowaniem punktów stałych, na przykład równowagi Nasha. Przydaje się lista Shivy: cs.princeton.edu/~kintali/ppad.html
András Salamon

Odpowiedzi:

47

Wykazanie, że masz problem z CoAM (lub SZK), jest rzeczywiście jednym z głównych sposobów przedstawienia dowodów na „stan zawieszenia twardości”. Ale poza tym istnieje kilka innych:

  • Pokaż, że twój problem dotyczy NP ∩ coNP. (Przykład: faktoring).
  • Pokaż, że twój problem można rozwiązać w quasipolynomialnym czasie. (Przykłady: wymiar VC, przybliżenie bezpłatnych gier).
  • Pokaż, że Twój problem nie jest trudniejszy niż odwrócenie funkcji jednokierunkowych lub rozwiązanie NP średnio. (Przykłady: wiele problemów w kryptografii.)
  • Pokaż, że Twój problem ogranicza się do (np.) Unikalnych gier lub rozszerzenia małego zestawu.
  • Pokaż, że Twój problem dotyczy BQP. (Przykład: Faktoring, choć oczywiście również w NP ∩ coNP.)
  • Wyklucz duże klasy redukcji kompletności NP. (Przykład: problem minimalizacji obwodu, zbadany przez Kabanets i Cai.)

Jestem pewien, że są inne, o których zapominam.

Scott Aaronson
źródło
2
To doskonała lista, Scott!
Suresh Venkat
1
Ciekawe ... która z tych technik pokazuje, że problem prawdopodobnie nie zostanie rozwiązany w czasie wielomianowym (RP, BPP)? Nie widziałem żadnego, który zdawałby się to robić.
Philip White
2
Philip: Masz rację, oni nie. Aby przedstawić dowody, że określonego problemu NP nie ma w P, wszystko sprowadza się do (1) próby umieszczenia go w P i niepowodzenia i / lub (2) zmniejszenia innych problemów, których ludzie nie włożyli w P do tego problemu.
Scott Aaronson
23

Z powyższego komentarza: jeśli problem wydaje się wystarczająco trudny, ale nie jesteś w stanie udowodnić, że jest on NP-zupełny, szybkie sprawdzenie polega na policzeniu liczby ciągów długości w języku: jeśli zestaw jest rzadki, to jest raczej nie jest NPC, w przeciwnym razie P = NP według twierdzenia Mahaneyan ... więc lepiej skierować wysiłki na udowodnienie, że jest w P :-) :-)

Przykładem jest problem dzielenia liczb na k-boxy (z bloga Fortnow & Gasarch, oryginalne źródło: Cyberpuzzles Doktora Ecco ):

{ 1 , . . . , n }  do co najwyżej k pól, aby żadne pole nie zawierało  x , y , z  dla  x + y = z }{(n,k) istnieje sposób na partycjonowanie  {1,...,n} do co najwyżej k pól, tak aby żadne pole nie miało x,y,z z x+y=z}

Marzio De Biasi
źródło
23

Oto trzy dodatki do listy Scotta:

  • Pokaż, że twój problem występuje w kilku P. Oznacza to, że liczba rozwiązań jest ograniczona pewnym wielomianem. (Przykład: problem z rogatkami). Nie wiadomo, że problem z kompletną NP występuje w kilku P. (niemożliwe, chyba że kilka P = NP).
  • LOGNPNP[log2n] (Można rozwiązać przy użyciu ograniczonej liczby niedeterministycznych bitów, przykład Dominujący problem z zestawem w turniejach)
  • 2nϵNPϵ>0n02nϵn

coNPNP/poly

Mohammad Al-Turkistany
źródło
1
Lub nawet w UP (nie tylko FewP)!
Joshua Grochow