Klasa złożoności odpowiadająca sortowaniu

Dwie części TCS to algorytmy i złożoność. Upraszczając powiem, że algorytmy to badanie górnych granic, pokazujące, że możesz coś zrobić (przy danych ograniczonych zasobach), a złożoność polega na pokazaniu, że nie możesz tego zrobić bez minimalnych zasobów.

Tak często problem algorytmiczny pojawia się w modelu decyzyjnym, aby umieścić go w klasie złożoności.

Ale zawsze mi przeszkadzało, że niektóre elementarne algorytmy nigdy nie są wprost wymienione jako należące do określonej klasy. Jednym z przykładów jest sortowanie (porównanie). Staram się, jak mogę, odpowiednia klasa wydaje się po prostu zbyt słaba (tak naprawdę, czy to po prostu sprawdzanie w dzienniku, że wynik jest sortowany? To po prostu wydaje się zbyt słabe, czy też nie mam poprawnej wersji decyzji).

Jaka jest najlepsza / najbardziej odpowiednia / najbardziej użyteczna klasa złożoności, w której znajduje się sortowanie porównawcze?

cc.complexity-theory sorting Mitch
źródło

Odpowiedzi:

Sortowania problemem jest faktycznie kompletne na $\mathsf{TC}^0$ (w -redukcja). Standardowym źródłem tego jest Rozdział 1.4.3 książki Vollmera . $\mathsf{AC}^0$

Zauważ, że jest klasą problemów decyzyjnych, ale zwykle myślimy o sortowaniu jako problemie funkcji, tzn. Chcemy wypisywać liczby, powiedzmy, w kolejności nie malejącej. Możemy jednak zdefiniować sortowanie jako problem decyzyjny w następujący sposób: $\mathsf{TC}^0$

Biorąc pod uwagę ciąg liczb i dwie liczby , chcemy zdecydować, czy jest w pozycji w kolejności otrzymujemy sortując w niemalejącą zamówienie. Należy zauważyć, że w celu uniknięcia niejasności, gdy , chcemy poprzedzać jeśli . $a_1,\ldots,a_n$ $k,p\in [n]$ $a_k$ $p$ $a_1,\ldots,a_n$ $a_i=a_j$ $a_i$ $a_j$ $i<j$

Dai Le
źródło

Doskonałe ... określone jako jaki problem formalnej decyzji?

Mitch

Umieszczenie odniesienia w odpowiedzi byłoby podwójnie doskonałe.

Oleksandr Bondarenko

@Mitch i @Okeksandr: Dziękujemy za komentarze! Właśnie przedłużyłem swoją odpowiedź, aby wyjaśnić te kwestie.

Dai Le

To brzmi jak problem decyzyjny dla statystyk zamówień. Czy istnieje powiązany problem, w którym wszystko jest na swoim miejscu? Coś jak podano sekwencję

i permutacja

decyduje, czy

. To jest tak trudne jak twoje; czy dla klasy obejmującej jest to trudniejsze czy kompletne?

a_{1} . . . a_{n}

$a_1...a_n$

σ

$\sigma$

[1.. n]

$[1..n]$

\forall_{1 \leq k < j \leq n}, a_{σ_{k}} < a_{σ_{j}}

$\forall_{1\le k\lt j\le n}, a_{\sigma_k} < a_{\sigma_j}$

Mitch

@Mitch: Uważam, że sprawdzenie, czy wszystko jest w odpowiednim miejscu, jest w rzeczywistości łatwiejsze niż sortowanie. Intuicja jest to, że można sprawdzić, że

dla wszystkich możliwych par

równolegle, co uważam, że można to zrobić w

. W przypadku powyższego problemu związanego z sortowaniem musisz „policzyć”, aby ustalić prawidłową pozycję liczby w porządku liniowym.

a_{σ_{k}} < a_{σ_{j}}

$a_{\sigma_k}<a_{\sigma_j}$

(a_{σ_{k}}, a_{σ_{j}})

$(a_{\sigma_k},a_{\sigma_j})$

k < j

$k<j$

{A C}^{0}

$\mathsf{AC}^0$

Dai Le

Wierzę, że FP jest tym, czego szukasz.

Nicholas Mancuso
źródło

Cóż, raczej szukam odpowiedniej klasy złożoności decyzji niż funkcjonalnej, ale mimo to jestem całkiem pewien, że sortowanie porównawcze nie jest bliskie P-complete (lub FP-complete), więc oczekuję mniejsza klasa, dla której oczekuje się jej ukończenia.

Mitch

Nie wiedziałem, że kompletność była jednym z wymogów twojego pytania. Jako problem decyzyjny (jeśli zignorujesz swoje ograniczenie kompletności), dlaczego P nie byłoby akceptowalne jako odpowiedź? Biorąc pod uwagę DTM, możesz zarówno wyprodukować, jak i zweryfikować certyfikat w czasie wielomianowym.

Nicholas Mancuso,

Biorąc pod uwagę ogólny problem, to, co zwykle chcę wiedzieć, to nie tylko to, że jest to czas wielomianowy, ale najmniejsza klasa, w jakiej mógłby się znaleźć. Chciałbym wiedzieć, czy to jest w LOGCFL, NL, L, AC_0 itp. Kompletność to jeden ze sposobów, w jaki „nie możesz” nic lepszego. Więc nit nie jest wymogiem mojego pytania, ale prawdopodobną odpowiedzią.

Mitch,