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 P 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}$

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.$\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.

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.

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 ):

{ 1 , . . . , n }  do co najwyżej k pól, aby żadne pole nie zawierało  x , y , z  dla  x + y = z $\{ (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 \}$

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$