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

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

Pokaż, że problem dotyczy GI (GI = Graph Isomorphism)
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. $\mathsf{co-AM}$

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

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

@MarzioDeBiasi brzmi dla mnie jak odpowiedź.

— Sasho Nikolov

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 dla Ricky Demer; możemy chcieć mieć listę metod dla pierwszej części.

— Pteromys

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:

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

To doskonała lista, Scott!

— Suresh Venkat

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

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

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 Mahaneya $n$ ... 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 ):

$\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$

— Marzio De Biasi
źródło

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).
$LOGNP$ $NP[log^2n]$ (Można rozwiązać przy użyciu ograniczonej liczby niedeterministycznych bitów, przykład Dominujący problem z zestawem w turniejach)
$2^{n^{\epsilon}}$ $NP$ $\epsilon \gt 0$ $n\ge 0$ $2^{n^{\epsilon}}$ $n$

$coNP ⊆ NP/poly$

— Mohammad Al-Turkistany
źródło

Lub nawet w UP (nie tylko FewP)!

— Joshua Grochow