Czy istnieją algorytmy czasu podwykładniczego dla problemów NP-zupełnych?

51

Czy istnieją problemy NP-zupełne, które dowiodły algorytmów podwykładniczych?

Proszę o ogólne informacje na temat spraw, nie mówię tutaj o przypadkach specjalnych, które można zastosować.

Pod wykładniczo rozumiem porządek wzrostu powyżej wielomianów, ale mniejszy niż wykładniczy, na przykład . $n^{\log n}$

— ksb
źródło

10

Co rozumiesz przez „sub wykładniczy”? Jeśli masz na myśli , odpowiedź brzmi zdecydowanie tak. Jeśli masz na myśli , uważam, że odpowiedź brzmi „nie”.

2^{o (n)}

$2^{o(n)}$

2^{n^{o (1)}}

$2^{n^{o(1)}}$

— JeffE

57

Zależy od tego, co rozumiesz przez podwykładniczy. Poniżej wyjaśniam kilka znaczeń „podwykładniczego” i co dzieje się w każdym przypadku. Każda z tych klas jest zawarta w klasach poniżej.

I. $2^{n^{o(1)}}$

Jeśli przez podwykładnik masz na myśli , to hipoteza w teorii złożoności o nazwie ETH (hipoteza wykładnicza) sugeruje, że żaden problem z może mieć algorytmu z czasem działania . $2^{n^{o(1)}}$ $\mathsf{NP}$ $2^{n^{o(1)}}$

Zauważ, że ta klasa jest zamknięta w składzie z wielomianami. Jeśli dysponujemy algorytmem podwykładniczym dla dowolnego problemu z , możemy połączyć go z redukcją czasu wielomianowego z SAT do uzyskania algorytmu podwykładniczego dla 3SAT, który naruszałby ETH. $\mathsf{NP}$

II. , tj. dla wszystkich $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $0 < \epsilon$

Sytuacja jest podobna do poprzedniej.

Jest zamknięty pod wielomianami, więc nie można w tej chwili rozwiązać problemu bez naruszenia ETH. $\mathsf{NP}$

III. , tj. dla niektórych $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $\epsilon < 1$

Jeśli przez podwykładniczy masz na myśli dla jakiegoś wtedy odpowiedź brzmi tak, istnieją prawdopodobnie takie problemy. $2^{O(n^\epsilon)}$ $\epsilon<1$

Weźmy -kompletny problem, taki jak SAT. Ma algorytm brutalnej siły, który działa w czasie . Rozważ teraz wyściełaną wersję SAT, dodając ciąg wejściowy o rozmiarze do danych wejściowych: $\mathsf{NP}$ $2^{O(n)}$ $n^k$

S A T^{'} = {⟨ φ, w ⟩ ∣ φ \in S A T and | w | = | φ |^{k}}

$SAT' = \{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \}$

Teraz ten problem jest -trwały i można go rozwiązać w czasie . $\mathsf{NP}$ $2^{O(n^\frac{1}{k})}$

IV. $2^{o(n)}$

Zawiera poprzednią klasę, odpowiedź jest podobna.

V. , tj. dla wszystkich $\bigcap_{0 < \epsilon}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon>0$

Zawiera poprzednią klasę, odpowiedź jest podobna.

VI. , tj. dla niektórych $\bigcup_{\epsilon < 1}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon<1$

Zawiera poprzednią klasę, odpowiedź jest podobna.

Co oznacza podwykładniczy?

„Powyżej wielomianu” nie jest górną granicą, ale dolną granicą i jest określane jako superpolinomia .

Funkcje takie jak są nazywane quasipolynomial , a jak sama nazwa wskazuje, są prawie wielomianowe i dalekie od wykładniczego, podwykładnicze zwykle stosuje się w odniesieniu do znacznie większej klasy funkcji o znacznie szybszych szybkościach wzrostu. $n^{\lg n}$

Jak wskazuje nazwa, „podwykładniczy” oznacza wolniejszy niż wykładniczy . Przez wykładniczy rozumiemy zwykle funkcje w klasie lub w lepszej klasie (która jest zamknięta w składzie z wielomianami). $2^{\Theta(n)}$ $2^{n^{\Theta(1)}}$

Subexponetialne powinny być do nich zbliżone, ale mniejsze. Można to zrobić na różne sposoby i nie ma standardowego znaczenia. Możemy zastąpić przez w dwóch definicjach wykładniczej i otrzymać I i IV. Zaletą jest to, że są one jednolicie zdefiniowane (brak kwantyfikatora nad ). Możemy zastąpić współczynnikiem multiplikatywnym dla wszystkich , otrzymujemy II i V. Są zbliżone do I i IV, ale niejednoznacznie zdefiniowane. Ostatnią opcją jest zastąpienie stałą multiplikatywną dla niektórych . To daje II i VI. $\Theta$ $o$ $\epsilon$ $\Theta$ $\epsilon$ $\epsilon>0$ $\Theta$ $\epsilon$ $\epsilon<1$

To, co należy nazwać subeksponencjalnym, jest dyskusyjne. Zwykle ludzie używają tego, czego potrzebują w swojej pracy i nazywają to subkonsolidacyjnym.

Jestem moją osobistą preferencją, jest to fajna klasa: jest zamknięta w składzie z wielomianami i jest jednolicie zdefiniowana. Jest podobny do który używa . $\mathsf{Exp}$ $2^{n^{O(1)}}$

Wydaje się, że II jest używany w definicji klasy złożoności . $\mathsf{SubExp}$

III jest stosowany do algorytmicznych górnych granic, takich jak te wymienione w odpowiedzi Pal.

IV jest również powszechne.

V służy do określenia hipotezy ETH.

Przecięcia ( II i V ) nie są tak przydatne w algorytmicznych górnych granicach, ich głównym zastosowaniem wydaje się teoria złożoności. W praktyce nie będzie widać różnicę między I i II lub między IV i V . IMHO trzy późniejsze definicje ( IV , V , VI ) są zbyt wrażliwe, mogą być przydatne w przypadku konkretnych problemów, ale nie są niezawodne, co zmniejsza ich przydatność jako klas. Solidność i dobre właściwości zamykania są jednym z powodów, dla których znane klasy złożoności, takie jak , , , $\mathsf{L}$ $\mathsf{P}$ $\mathsf{NP}$ $\mathsf{PSpace}$ i są interesujące. $\mathsf{Exp}$

Letni

IMHO, główne definicje to I i III . Mamy już algorytmy podwykładnicze dla problemów w sensie III i nie możemy mieć ich w sensie I bez naruszenia ETH. $\mathsf{NP}$

— Kaveh
źródło

7

Ta odpowiedź powinna przejść do Wikipedii.

— Erel Segal-Halevi

32

Wystarczy wymienić niektóre, wszystkie z czasem pracy mniej więcej lub : $2^{O(\sqrt{n} \log n)}n^{O(1)}$ $2^{O(\sqrt{n})}n^{O(1)}$

Zestaw informacji zwrotnych na temat turniejów [Noga Alon, Daniel Lokshtanov, Saket Saurabh, ALP 2009]
Minimalne wypełnienie i zakończenie łańcucha [Fomin and Villanger SODA 2012]
Usuwanie krawędzi podziału [Ghosh i in. SWAT 2012]
Edycja klastrów za pomocą klastrów $t$ [Fomin i in. STACS 2013]
Wiele problemów z dwuwymiarowością, różne problemy z grafami na grafach z ograniczonym rodzajem, a zwłaszcza z grafami planarnymi (patrz Demaine, Fomin, Hajiaghayi, Thilikos: Sparametryzowane algorytmy subwykładnicze na grafach z grafem z ograniczonym rodzajem i grafy wolne od H-moll )
Algorytm parametryzowany w czasie podwykładniczym dla drzewa Steinera na wykresach planarnych [Pilipczuk i in. STACS 2013]
Trywialnie doskonałe uzupełnienie, ukończenie progu i ukończenie Pseudosplit [D. i in. STACS 2014]
Zakończenie interwału [Bliznets i in.]
Prawidłowe zakończenie interwału [Bliznets i in.]

— Pål GD
źródło

1

Uwaga: te algorytmy są czasem podwykonawczym w tym sensie, że działają w czasie (dla niektórych ), ale nie w tym sensie, że działają w czasie .

2^{O (n^{ϵ})}

$2^{O(n^\epsilon)}$

ϵ < 1

$\epsilon<1$

2^{n^{o (1)}}

$2^{n^{o(1)}}$

— Kaveh

Czy istnieją algorytmy czasu podwykładniczego dla problemów NP-zupełnych?

I.2no(1)2no(1)2^{n^{o(1)}}

II. , tj. dla wszystkich 2 O ( n ϵ ) 0 < ϵ⋂0<ϵ2O(nϵ)⋂0<ϵ2O(nϵ)\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}2O(nϵ)2O(nϵ)2^{O(n^\epsilon)} 0<ϵ0<ϵ0 < \epsilon

III. , tj. dla niektórych 2 O ( n ϵ ) ϵ < 1⋃ϵ<12O(nϵ)⋃ϵ<12O(nϵ)\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}2O(nϵ)2O(nϵ)2^{O(n^\epsilon)} ϵ<1ϵ<1\epsilon < 1

IV. 2o(n)2o(n)2^{o(n)}

V. , tj. dla wszystkich⋂0<ϵ2ϵn⋂0<ϵ2ϵn\bigcap_{0 < \epsilon}2^{\epsilon n}2ϵn2ϵn2^{\epsilon n} ϵ>0ϵ>0\epsilon>0

VI. , tj. dla niektórych⋃ϵ<12ϵn⋃ϵ<12ϵn\bigcup_{\epsilon < 1}2^{\epsilon n}2ϵn2ϵn2^{\epsilon n} ϵ<1ϵ<1\epsilon<1

Co oznacza podwykładniczy?

I. $2^{n^{o(1)}}$

II. , tj. dla wszystkich $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $0 < \epsilon$

III. , tj. dla niektórych $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $\epsilon < 1$

IV. $2^{o(n)}$

V. , tj. dla wszystkich $\bigcap_{0 < \epsilon}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon>0$

VI. , tj. dla niektórych $\bigcup_{\epsilon < 1}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon<1$