Czy może istnieć wyjątkowo duży ukryty podzbiór problemów wielomianowo możliwych do rozwiązania w ramach problemów NP-Complete?

Załóżmy, że P! = NP.

Wiemy, że w każdej chwili możemy wykonać proste instancje 3-SAT. Możemy również wygenerować coś, co uważamy za trudne wystąpienie (ponieważ nasze algorytmy nie potrafią ich szybko rozwiązać). Czy jest coś, co przeszkadza, by zbiór twardych instancji był arbitralnie mały, o ile dla dowolnej wielkości instancji (n) istnieją tylko instancje Poly (n) (lub nawet stałe) o wielkości Poly (n) lub mniejszej?

W przypadku każdej twardej instancji 3-SAT musielibyśmy dodać zestaw wszystkich instancji 3-SAT, do których redukuje się poprzez zapętlenie w cyklu redukcji NP-Completeness, ale nie przewiduję, że to bardzo zwiększy liczbę twardych instancji .

W tym świecie moglibyśmy stworzyć algorytm, który wielomianowo rozwiązuje wszystkie problemy NP całkowite, z wyjątkiem kilku wyjątkowych.

Edycja: Łagodniejszy wariant pytania: nawet jeśli pokazaliśmy P! = NP, skąd możemy wiedzieć, czy dana metoda generowania problemów n 3-SAT faktycznie generowała trudny z pewnym wymaganym prawdopodobieństwem? Jeśli nie ma sposobu, aby dowiedzieć się z samego P! = NP, co jest wymagane, aby pokazać, że możemy wygenerować trudny problem NP-zupełny?

1) W zależności od tego, co dokładnie oznaczono, wnioski z obserwacji Kaveha można wzmocnić $\mathsf{NP} \subseteq \mathsf{P/poly}$ do $\mathsf{P} = \mathsf{NP}$, zasadniczo używając Twierdzenia Mahaneya. To znaczy, jeśli istnieje algorytm, który rozwiązuje SAT i działa w czasie$\leq p(n)$ we wszystkich przypadkach długości $n$ z wyjątkiem ewentualnie $q(n)$ takie przypadki, gdzie $p$ i $q$ w rzeczywistości są to wielomiany $\mathsf{P} = \mathsf{NP}$. Patrz np. Meyer i Paterson i odnośniki w nim, lub monografia Schoninga „Złożoność i struktura” . Więc jeśli to uchwyci twoje pojęcie „trudnych instancji”, to musi być ich więcej niż$poly(n)$ wiele trudnych instancji dla każdego $n$, zakładając $\mathsf{P} \neq \mathsf{NP}$.

Do Twojej wiadomości, takie algorytmy są czasami nazywane algorytmami „apt” lub „APT”, dla „prawie wielomianowego czasu” (nie mylić z bardziej nowoczesną klasą złożoności $\mathsf{almostP}$, która jest równa $\mathsf{BPP}$).

2) Powyższe można dodatkowo wzmocnić w następujący sposób. Założyć$\mathsf{P} \neq \mathsf{NP}$. Zatem powyższe mówi, że dla każdego algorytmu rozwiązującego SAT i dowolnego wielomianu$p$, istnieje zestaw instancji wielkości wielomianowej, na których algorytm zajmuje więcej niż $p(n)$czas. Ale zestaw może zależeć od algorytmu.

Silniejszy wynik przełącza kwantyfikatory i dochodzi do wniosku: istnieje zestaw wielomianów wielkości H (dla „twardego”), taki że dla dowolnego algorytmu A rozwiązującego SAT i dowolnego wielomianu p, A zajmuje więcej niż $p(n)$czas na wszystkich, ale skończonych, wielu elementach H. Taki H nazywany jest rdzeniem złożoności (założenie wielkości nie jest częścią definicji rdzenia złożoności). Definicja i istnienie rdzeni złożoności została podana przez Lyncha . Wynik, który właśnie cytowałem, potwierdzają Orponen i Schoning .

Nikt nie wspomniał o słynnym artykule Impagliazzo „Pięć światów”.

http://www.cs.ucsd.edu/users/russell/average.ps

inny punkt widzenia na to pytanie (poza odniesieniem do twierdzenia Mahaneya). „punkt przejściowy” w SAT jest badaniem tego zjawiska rozkładu łatwych i trudnych przypadków, szczególnie wokół „punktu krytycznego”, w którym prawdopodobieństwo wystąpienia trudnych przypadków jest zmaksymalizowane. literatura na ten temat jest długa i złożona. ma zarówno podejście empiryczne, jak i analityczne. ma głębokie powiązania z fizyką / termodynamiką. [3] niestety obecnie nie ma wpisu na Wikipedię na ten bardzo znaczący i fundamentalny temat teorii złożoności. wydaje się również, że nie ma wielu ogólnych ani „standardowych” badań na ten temat. oto jedna ostatnia informacja, aby rozpocząć na SAT [1] i ogólnie przejściach faz TCS. [4] twoje pytanie również należy do kategorii „naprawdę dobra odpowiedź to w zasadzie prawie P$\stackrel{?}{=}$Dowód NP ”.

Czy jest coś, co uniemożliwia zestawowi twardych instancji, aby były arbitralnie małe, o ile dla dowolnej wielkości instancji (n) istnieją tylko instancje Poly (n) (lub nawet stałe) o wielkości Poly (n) lub mniejszej?

ponownie twierdzenie Mahaneya (sformułowane nieco inaczej) odpowiada na to bezpośrednio. innym sposobem spojrzenia na to jest to, że próby zawężenia rozkładu instancji w jakiś kluczowy / charakterystyczny sposób prowadzą do funkcji NP-complete. przykładem tego ze złożoności obwodu monotonicznego są „funkcje wycinania”. [2]

[1] Przewidywanie satysfakcji na etapie przejścia Lin Xu, Holger H. Hoos, Kevin Leyton-Brown

[2] Paul ES Dunne: Złożoność funkcji centralnego wycinania. Teoria Comput. Sci. 44: 247-257 (1986)

[3] Analityczne i algorytmiczne rozwiązanie problemów losowej satysfakcji M. Mezard, G. Parisi, R. Zecchina

[4] Przejścia fazowe w problemach NP-zupełnych: wyzwanie dla prawdopodobieństwa, kombinatoryki i informatyki autorstwa Moore'a