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 .
Odpowiedzi:
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.2no(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 .2no(1) 2 n o ( 1 )NP 2no(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.NP
II. , tj. dla wszystkich 2 O ( n ϵ ) 0 < ϵ⋂0<ϵ2O(nϵ) 2O(nϵ) 0<ϵ
Sytuacja jest podobna do poprzedniej.
Jest zamknięty pod wielomianami, więc nie można w tej chwili rozwiązać problemu bez naruszenia ETH.NP
III. , tj. dla niektórych 2 O ( n ϵ ) ϵ < 1⋃ϵ<12O(nϵ) 2O(nϵ) ϵ<1
Jeśli przez podwykładniczy masz na myśli dla jakiegoś wtedy odpowiedź brzmi tak, istnieją prawdopodobnie takie problemy. ϵ < 12O(nϵ) ϵ<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:2 O ( n ) n kNP 2O(n) nk
Teraz ten problem jest -trwały i można go rozwiązać w czasie .NP 2O(n1k)
IV.2o(n)
Zawiera poprzednią klasę, odpowiedź jest podobna.
V. , tj. dla wszystkich⋂0<ϵ2ϵn 2ϵn ϵ>0
Zawiera poprzednią klasę, odpowiedź jest podobna.
VI. , tj. dla niektórych⋃ϵ<12ϵn 2ϵn ϵ<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.nlgn
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Θ(n) 2nΘ(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.Θ o ϵ Θ ϵ ϵ>0 Θ ϵ ϵ<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 .Exp 2nO(1)
Wydaje się, że II jest używany w definicji klasy złożoności .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 , , ,L P NP PSpace i są interesujące.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.NP
źródło
Wystarczy wymienić niektóre, wszystkie z czasem pracy mniej więcej lub :2O( √2O(n√logn)nO(1) 2O(n√)nO(1)
źródło