Optymalne solwery NP

Napraw problem wyszukiwania NP-complete, np. Formularz wyszukiwania SAT. Wyszukiwanie Levin zapewnia algorytm do rozwiązywania który jest w pewnym sensie optymalny. Konkretnie, algorytm jest „Wykonanie wszystkich możliwych programów w zazębianie na wejściowego , gdy niektórzy powraca odpowiedzieć testy czy jest to poprawna”. Jest optymalna w tym sensie, że biorąc pod uwagę programu , który rozwiązuje z Złożoność , czas złożoność z spełnia $X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$ $L$ $X$ $P$ $x$ $P$ $y$ $P$ $X$ $t_P(n)$ $t_L(n)$ $L$

t_{L} (n) < 2^{| P |} p (t_{P} (n))

$t_L(n) < 2^{|P|}p(t_P(n))$

gdzie jest stałym wielomianem, który zależy od dokładnego modelu obliczeniowego $p$

$L$ Optymalność można sformułować w nieco mocniejszy sposób. Mianowicie dla każdego i Program rozwiązywania obiecująco w czasie , złożoność czas z ograniczony do wejść w spełnia $M \subset \lbrace 0,1 \rbrace^*$ $Q$ $X$ $M$ $t^M_Q(n)$ $t_L^M(n)$ $L$ $M$

t_{L}^{M} (n) < 2^{| Q |} q (n, t_{Q}^{M} (n))

$t_L^M(n) < 2^{|Q|}q(n, t^M_Q(n))$

gdzie jest stałym wielomianem. Zasadnicza różnica polega na tym, że może być np. Wielomianem, nawet jeśli $q$ $t^M_Q(n)$ $P \neq NP$

Oczywistą „słabością” jest duży współczynnik w tym zakresie. Łatwo zauważyć, że jeśli istnieje algorytm spełniający granicę tego samego formularza z zastąpionym wielomianem wnastępnie . Wynika to z faktu, że możemy uznać za program rozwiązujący daną instancję poprzez zakodowanie odpowiedzi na stałe. Podobnie, jeśli można zastąpić funkcją sub wykładnicząwówczas hipoteza wykładniczego czasu jest naruszana. Jednak odpowiedź na następujące pytanie jest mniej oczywista (dla mnie): $L$ $2^{|Q|}$ $2^{|Q|}$ $|Q|$ $P = NP$ $Q$ $X$ $2^{|Q|}$ $|Q|$

Zakładając hipotezę wykładniczego czasu i inne dobrze znane przypuszczenia (np. Brak degeneracji hierarchii wielomianowej, istnienie funkcji jednokierunkowych), jeśli to konieczne, czy istnieje algorytm rozwiązujący st dla każdego i program rozwiązywania obiecująco w czasie , złożoność czas z ograniczona do wejść w spełnia $A$ $X$ $M \subset \lbrace 0,1 \rbrace^*$ $Q$ $X$ $M$ $t^M_Q(n)$ $t_A^M(n)$ $A$ $M$

$t_{A}^{M} (n) < f (| Q |) q (n, t_{Q}^{M} (n)) + g (| Q |)$ $t_A^M(n) < f(|Q|)q(n, t^M_Q(n)) + g(|Q|)$
gdzie jest wielomianem, jest subwykładniczy, a jest arbitralny $q$ $f$ $g$

Jeśli odpowiedź jest pozytywna, czy może być wielomianowe? Jaka jest stopa wzrostu (wyraźnie co najmniej wykładniczo pod ETH)? Jeśli odpowiedź jest przecząca, czy może istnieć wielomian , jeśli ETH jest błędne, ale ? $f$ $g$ $f$ $P \neq NP$

cc.complexity-theory time-complexity p-vs-np

— Vanessa
źródło

Rozważ następujący algorytm (wariant algorytmu Levina):

Uruchom równolegle pierwsze algorytmów. Dodatkowo uruchom równolegle algorytm brutalnej siły, który wypróbowuje wszystkie możliwe rozwiązania jeden po drugim. (Uruchom wszystkie algorytmy z tą samą prędkością.) $n$

Zatrzymaj się, gdy jeden z algorytmów znajdzie rozwiązanie.

Rozważ dwa przypadki (biorąc pod uwagę wejściowej długości ): $x$ $n$

$Q$ jest jednym z pierwszych algorytmów. Następnie czas działania to . $n$ $O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$
$Q$ nie jest jednym z pierwszych algorytmów (a więc ). Następnie czas działania jest ograniczony przez czas działania algorytmu brutalnej siły. Mamy czas działania . $n$ $n < 2^{|Q|}$ $2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$

Mamy

t_{A}^{M} (n) \leq p o l y (n) \cdot t_{Q}^{M} (n) + 2^{2^{O (| Q |)}} .

$t^M_A(n) \leq \mathrm{poly}(n) \cdot t^M_Q(n) + 2^{2^{O(|Q|)}}.$

(Tutaj jest wielomianem, a jest podwójnie wykładnicze w ; możemy poprawić zależność od , pogarszając zależność od .) $f(n)$ $g(n)$ $n$ $g(n)$ $n$ $f(n)$ $n$

— Yury
źródło

Istnieje wariant tego, który w pewnym sensie lepiej spełnia ograniczenia, chociaż nie jest to forma, o którą prosiłem. Mianowicie, zamiast używać algorytmu brute-force, uruchom zwykłe wyszukiwanie Levin. Daje to to samo ograniczenie z drugim terminem zastąpionym przez ~

2^{| Q |} t_{Q}^{M} (2^{| Q |})

$2^{|Q|}t^M_Q(2^{|Q|})$

— Vanessa