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,