Klasy złożoności dla przypadków innych niż „najgorszy przypadek”

Czy mamy klasy złożoności w odniesieniu do, powiedzmy, złożoności średnich przypadków? Na przykład, czy istnieje (nazwana) klasa złożoności dla problemów, których podjęcie wymaga wielomianu?

Kolejne pytanie dotyczy złożoności najlepszych przypadków , których przykłady przedstawiono poniżej:

Czy istnieje klasa (naturalnych) problemów, których decyzja wymaga co najmniej wykładniczego czasu?

Aby to wyjaśnić, zastanów się nad językiem uzupełnionym o EXP . Oczywiście nie wszystkie wystąpienia wymagają czasu wykładniczego: Istnieją przypadki, które można rozstrzygnąć nawet w czasie wielomianowym. Zatem najlepszą złożonością przypadku nie jest czas wykładniczy.$L$$L$$L$

EDYCJA: Ponieważ pojawiło się kilka niejasności, chcę spróbować wyjaśnić to jeszcze bardziej. Przez złożoność „najlepszego przypadku” rozumiem klasę złożoności, której złożoność problemów jest ograniczona przez jakąś funkcję. Na przykład zdefiniuj BestE jako klasę języków, których nie można ustalić w czasie krótszym niż pewien liniowy wykładniczy. Symbolicznie niech oznacza dowolną maszynę Turinga, a , i będą liczbami naturalnymi:c n 0$M$$c$$n_0$$n$

$L \in \mathbf{BestE} \Leftrightarrow$ $\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

gdzie oznacza czas potrzebny do zatrzymania się na wejściu .M $T(M(x))$$M$$x$

Zgadzam się, że zdefiniowanie takiej klasy problemów jest bardzo dziwne, ponieważ wymagamy, aby każda maszyna Turinga , niezależnie od jej mocy, nie mogła decydować o języku w czasie krótszym niż jakiś liniowy wykładniczy.$M$

Zauważ jednak, że odpowiednik czasu wielomianowego ( BestP ) jest naturalny, ponieważ każda maszyna Turinga wymaga czasuprzynajmniej odczytać jego dane wejściowe.$|x|$

PS: Może zamiast kwantyfikować jako „dla całej maszyny Turinga ”, musimy ograniczyć ją do niektórych wcześniej określonych klas maszyn Turinga, takich jak maszyny Turinga z wielomianowym czasem. W ten sposób możemy zdefiniować klasy takie jak , która jest klasą języków wymagających co najmniej kwadratu czasu na decyzję na maszynach Turinga z czasem wielomianowym.B e s t ( n 2$M$$\mathbf{Best(n^2)}$

PS2: Można również rozważyć odpowiednik złożoności obwodu, w którym decydujemy o najmniejszym rozmiarze / głębokości obwodu, aby wybrać język.

Chociaż nie mogę dokładnie przeanalizować twoich definicji, powinieneś wiedzieć, że znane są znacznie silniejsze hierarchie czasu, w szczególności hierarchie czasu „prawie wszędzie”.

Oto formalne stwierdzenie: dla każdego czasu istnieje język L ∈ T I M E [ T ( n ) ] z właściwością, że każdy algorytm deterministyczny, który poprawnie rozpoznaje L, musi działać w czasie asymptotycznie większym niż t ( n ) na wszystkich, ale nieskończenie wielu wejściach, przez wystarczająco krótki czas t ( n ) . $T(n)$$L \in TIME[T(n)]$$L$$t(n)$$t(n)$

„Wystarczająco mały” oznacza .$t(n) \log t(n) \leq o(T(n))$

Załóżmy, że wybór dla przykładu i uzyskania języka twardego L . Następnie każdy algorytm, który poprawnie rozpoznaje L, musi zająć co najmniej 2 n / n 2 czasu na wszystkich wejściach o określonej długości. To wydaje się być tym, czego szukasz w swojej klasie BestE.$T(n)=2^n$$L$$L$$2^n/n^2$

Odniesienie:

John G. Geske, Dung T. Huynh, Joel I. Seiferas: Uwaga na temat prawie kompleksowych zestawów i oddzielania klas deterministyczno-złożoności Inf. Comput. 92 (1): 97–104 (1991)

Istnieje szereg klas, które próbują zmierzyć się z różnymi pojęciami złożonej średniej wielkości przypadków. W Zoo Złożoności niektóre klasy, którymi możesz być zainteresowany, to:

Śr

HeurP

DistNP

(NP, P-samplable)

Arora / Barak obejmuje wiele podobnych klas (w rozdz. 18), definiujących distP, distNP i sampNP.

Dokładny związek między wszystkimi tymi klasami charakteryzuje Pięć Światów Impagliazza, o które wcześniej pytano w innym pytaniu .

Jeśli chodzi o pytanie o złożoność „najlepszego przypadku”, nie jestem pewien, czy rozumiem, co masz na myśli. Szukasz EXP ?

Jeśli masz na myśli klasy złożoności zdefiniowane w kategoriach najlepszego czasu działania wszystkich przypadków, nie jest to a priori bardzo dobra miara złożoności, ponieważ patrzysz tylko na trywialne przypadki dowolnego problemu.

[Rozszerzając odpowiedź Ryana Williamsa i dodając dla ciebie pewne wyszukiwane hasła] Twoje pojęcie najlepszej złożoności przypadku ma już nazwę: prawie wszędzie (ae) twardość lub odporność biologiczna. (Przykład Ryana jest -bi-odporność). Jeśli C jest klasa złożoności, a następnie język L jest C -immune jeśli nie ma nieskończony podzbiór L ' ⊆ L takie, że L ' ∈ C . L jest odporny na C, jeśli zarówno L, jak i jego dopełniacz ¯ $TIME[T(n)]$$\mathcal{C}$$L$$\mathcal{C}$$L' \subseteq L$$L' \in \mathcal{C}$$L$$\mathcal{C}$$L$ oznacza C- odporność. Na przykład nietrudno wykazać, że twoja definicja B e s t E jest równoważna klasie zbiorów E -odpornych.$\overline{L} = \Sigma^* \backslash L$$\mathcal{C}$$\mathbf{BestE}$$E$

(Na marginesie: pojęcie odporności zostało po raz pierwszy rozwinięte przez Posta w 1944 r. W teorii obliczeń, na długo przed zdefiniowaniem P. Post faktycznie uważano za „zbiory proste” - zbiór jest prosty, jeśli jego dopełnienie jest odporne. Dla teoretyków obliczeń, słowo „odporny” zwykle oznacza „odporny na zestawy obliczalne”. W tym ustawieniu odporność jest równoważna „zestawom odpornym na ce”, ponieważ każdy nieskończony zestaw ce zawiera nieskończony zestaw obliczeniowy. Uważam, że artykuł Posta był również pierwszym, który wprowadził pojęcie redukcji wielu, ale nie mogłem tego przysiąc.)

Różne przypadki mają większy sens, gdy mówimy o algorytmach, a nie problemach. Z drugiej strony klasy złożoności dotyczą problemów, a nie algorytmów. Dlatego klasa złożoności, która zawsze stanowi najgorszy przypadek dla dowolnego algorytmu, wynika z definicji.

Złożonym celem jest znajomość liczby zasobów potrzebnych do rozwiązania dowolnego wystąpienia danego problemu. Dlatego wiesz, że dla każdego wystąpienia i algorytmu będziesz potrzebować tych zasobów i nic więcej.

W analizie algorytmów Twoim celem jest upewnienie się, że algorytm ma górną granicę dla zasobu, w każdym przypadku problemu. Trywialną granicą jest klasa złożoności problemu, ponieważ żaden przydatny (niepotrzebny krok) algorytm nie zajmuje więcej czasu. Można jednak poprawić tę granicę, biorąc pod uwagę specyfikę algorytmu.

$\Theta$

Jeśli chodzi o najlepszy przypadek, dla każdego problemu znalezienie najmniejszej liczby potrzebnych zasobów jest banalne. Załóżmy, że wejście ma długość O (n), a wyjście o długości O (m). Następnie następujący TM M zawsze działa w O (n) + O (m) w najlepszym przypadku:

M {Dane wejściowe, wystąpienie, rozwiązanie}

1. Porównaj dane wystąpienie z wystąpieniem zakodowanym w komputerze.
2. Jeśli są równe, zwróć zakodowane rozwiązanie.
3. W przeciwnym razie przeszukaj brutalną siłę.

$O(1)$