pełny problem z quasi-wielomianem związanym z liczbą rozwiązań

FewP to klasa z wielomianem ograniczonym liczbą rozwiązań (w wielkości wejściowej). Tam nie jest znana -Complete problem . Interesuje mnie, jak daleko możemy rozciągnąć tę obserwację. $NP$ $NP$ $fewP$

Czy istnieje jakiś naturalny problem z uzupełnieniem z quasi-wielomianową górną granicą liczby rozwiązań (świadków)? Czy istnieje powszechnie przyjęte przypuszczenie, które wykluczałoby taką możliwość? $NP$

Naturalne oznacza, że problem nie jest sztucznie wymyślonym problemem, aby odpowiedzieć na pytanie (lub podobne), a ludzie są zainteresowani problemem niezależnie (zgodnie z definicją Kaveha).

EDYCJA: Nagroda zostanie przyznana za taki naturalny problem lub rozsądny argument wykluczający istnienie takich problemów (przy użyciu powszechnie akceptowanych teorii teoretycznych złożoności). $NP$

Motywacja: Moją intuicją jest to, że kompletność narzuca wielomian (a nawet wykładniczy) dolną granicę liczby świadków. $NP$

cc.complexity-theory np Mohammad Al-Turkistany
źródło

Problem obietnica UniqueSAT w

(nie jest takie samo jak

), który jest podzbiorem

(ale nie takie same, jak

) .

P r o m i s e U P

$\mathsf{PromiseUP}$

U P

$\mathsf{UP}$

P r o m i s e F e w P

$\mathsf{PromiseFewP}$

F e w P

$\mathsf{FewP}$

Joshua Grochow

Czy wypełnienie SAT odpowiada na twoje pytanie?

Kaveh

To jest cała sprawa - nie jest; rozmiar wejściowy to liczba bitów na wejściu, a (rzadkie) instancje 3-sat mają rozmiar

. Liczba zmiennych jest tylko jednym aspektem (parametrem) danych wejściowych, więc w przypadku innych problemów (powiedzmy problemów graficznych) należałoby określić, co mierzy się pod względem liczby świadków. Na przykład dla maksymalnego cięcia wykres wejściowy może mieć

krawędzi, i znowu są tylko

świadków (co ma podwykładniczy rozmiar wejściowy ). Ale naprawdę chcemy mierzyć w kategoriach

. Jednak nie jest oczywiste, że #vertices jest właściwą miarą.

m \log n

$m \log n$

n^{2}

$n^2$

2^{n}

$2^n$

n

$n$

Daniello

@Kaveh Tak, więc powinieneś założyć, że Mahomet pomyślał o tym, który ma sens w jego pytaniu. Jak widać, złożoność zoo zgadza się z moją definicją. Zasadniczo w żadnej interesującej klasie złożoności definicja nie powinna ulec zmianie, jeśli wprowadzisz dane wejściowe wielomianem.

domotorp

@downvoters Dlaczego, do diabła, ludzie rezygnują z tego pytania? Chodzi mi o to, że przynajmniej ktoś mógłby podać powód ...

domotorp

Odpowiedzi:

To bardzo interesujące pytanie.

Najpierw uwaga wyjaśniająca. Zauważ, że „górna granica liczby świadków” to nie właściwością obliczeniowej problemu per se, ale z konkretnym weryfikatora używane do decydowania o problemu, po prostu jako „górną granicę liczby państw” nie będzie właściwość problemu, ale decydująca jest maszyna Turinga. Zatem powiedzenie „ Problem z górną granicą liczby rozwiązań” nie jest dość dokładne, a jeśli to każdy problem ma weryfikator z dowolną liczbą pożądanych rozwiązań (w tym zero i wszystkie możliwe łańcuchy) . $NP$ $NP$ $P = NP$ $NP$

Musimy więc zdefiniować, aby odpowiedzieć na twoje pytanie. Dla , powiedzmy, że problem „ma co najwyżej rozwiązania”, jeżeli dla pewnej stałej istnieje weryfikator czasowy taki, że dla każdej długości wejściowej i dla co długości , są różne $s : {\mathbb N} \rightarrow {\mathbb N}$ $NP$ $L$ $s(n)$ $c$ $O(n^c)$ $V$ $n$ $x \in L$ $n$ O długości tak, żeakceptuje wszystkieiodrzuca wszelkie inneo długości . $y_1,\ldots,y_{s(n)}$ $n^c$ $V(x,y_i)$ $i$ $V(x,y)$ $y$ $n^c$

W tej chwili mogę tylko powiedzieć, że:

Każdy -Complete Problem wiem (zdefiniowany przez jakiegoś naturalnego weryfikatora) ma oczywisty odpowiadającą wersję -Complete liczenia (z tego samego weryfikatora). $NP$ $\#P$
Dla każdego -Complete problemu określonym z weryfikatorem o co najwyżej roztworu (lub nawet Solutions) odpowiadający wersji zliczania prawdopodobnie nie -Complete. $NP$ $poly(n)$ $2^{n^{o(1)}}$ $\#P$

Więcej szczegółów Przypuśćmy jest -Complete, za pomocą weryfikatora , który zawiera co najwyżej rozwiązań. Następnie naturalna licząca się wersja „decyzyjna” , którą definiujemy jako $L$ $NP$ $V$ $O(n^c)$ $L$

$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$

obliczeniowy jest w , to znaczy, w zależności polytime z zapytań do . To dlatego, decydując, czy liczba rozwiązań wynosi co najwyżej jest w : świadka, jeśli istnieje, to po prostu liczba „s czyniąc zaakceptować, co my wiemy być co najwyżej $FP^{NP[O(\log n)]}$ $O(\log n)$ $NP$ $x$ $k$ $NP$ $y_i$ $V$ $O(n^c)$ . Wtedy możemy Przeszukiwanie binarne za pomocą tego problemu obliczyć dokładną liczbę rozwiązań . $NP$ $L$

Dlatego też, -Complete problemem tego rodzaju nie może być rozszerzony do -Complete problem w zwykły sposób, o ile . Wygląda to mało prawdopodobne; cała wielomianowa hierarchia czasu po prostu zawaliłaby się do . $NP$ $\#P$ $\#P \subseteq FP^{NP[O(\log n)]}$ $P^{NP[O(\log n)]}$

Jeśli założysz w powyższym przypadku, nadal otrzymasz mało prawdopodobne konsekwencje. Można by pokazać, że można obliczyć w raz z wyroczni. To więcej niż wystarczy, aby na przykład udowodnić, że a następnie $s(n) = 2^{n^{o(1)}}$ $\#P$ $2^{n^{o(1)}}$ $NP$ $EXP^{NP} \neq PP$ $EXP^{NP} \not\subset P/poly$ . Nie dlatego, że te podziały są mało prawdopodobne, ale wydaje się mało prawdopodobne, że będą udowodnił dając czas subexp algorytm -oracle na stałe. $NP$

Nawiasem mówiąc, nie powiedziałem tutaj nic wnikliwego. W literaturze prawie na pewno jest taki argument.

Ryan Williams
źródło

Rzeczywiście jest to wnikliwa odpowiedź.

Mohammad Al-Turkistany