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 .nlogn

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”. 2o(n)2no(1)
JeffE

Odpowiedzi:

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.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 )NP2no(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 kNP2O(n)nk

SAT={φ,wφSAT and |w|=|φ|k}

Teraz ten problem jest -trwały i można go rozwiązać w czasie .NP2O(n1k)

IV. 2o(n)

Zawiera poprzednią klasę, odpowiedź jest podobna.

V. , tj. dla wszystkich0<ϵ2ϵn2ϵn ϵ>0

Zawiera poprzednią klasę, odpowiedź jest podobna.

VI. , tj. dla niektórychϵ<12ϵn2ϵ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 .Exp2nO(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 , , ,LPNPPSpace 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

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 :2O(2O(nlogn)nO(1)2O(n)nO(1)

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 . ϵ < 1 2 n o ( 1 )2O(nϵ)ϵ<12no(1)
Kaveh