Prosty dowód na najgorszy przypadek Ω (n lg n) wyjątkowości / odrębności?

Istnieje kilka dowodów na dolną granicę logiczną dla problemu wyjątkowości / odrębności elementu (opartej na drzewach obliczeń algebraicznych lub argumentach przeciwnych), ale szukam takiego, który byłby wystarczająco prosty do zastosowania w pierwszym kursie analizy i projektowania algorytmów. Taki sam „poziom trudności” jak dolna granica sortowania byłby w porządku. Również każde podejście (np. Kombinatoryczne lub oparte na teorii informacji) byłoby OK. Jakieś sugestie?

cc.complexity-theory lower-bounds proofs

— Magnus Lie Hetland
źródło

Jaki model obliczeń masz na myśli? Jeśli elementy są małymi liczbami całkowitymi, można zrobić

przez sortowanie. Jeśli elementy można porównać tylko pod kątem nierówności, wydaje się, że istnieje dolna granica

. Czy poprawnie jest wnioskować z odpowiedzi, której szukasz, że elementy są uporządkowane liniowo i mogą być porównywane dla <, =,>, ale żadnych innych operacji?

o (n \log n)

$o(n \log n)$

Ω (n^{2})

$\Omega(n^2)$

— Warren Schudy,

Pytanie Warrena w jego komentarzu to dobry telefon. W związku z tym komentarz Davida Eppsteina do innego pytania jest wnikliwy, w którym podkreśla on znaczenie określenia modelu obliczeniowego, gdy mówimy o tego rodzaju dolnych granicach. Nawiasem mówiąc, nie jestem pewien, czy ma sens zestawienie obok siebie „drzew obliczeń algebraicznych” (model obliczeń) i „argumenty kontradyktoryjne” (metoda sprawdzająca).

— Tsuyoshi Ito

Bardzo dobre punkty. Moja aplikacja wyjaśnia tutaj dowody twardości poprzez redukcję - na przykład poprzez redukcję od unikalności do sortowania (i kilka innych problemów). Dlatego zakładam te same podstawowe operacje, co podczas pracy z sortowaniem porównawczym (aby redukcja działała). (Lub, jak sądzę, cokolwiek równoważnego pamięci RAM z liczbami rzeczywistymi.)

— Magnus Lie Hetland

Odpowiedzi:

Każdy certyfikat (dowód) odrębności, który używa tylko <, = i>, musi zawierać porównania między każdą parą sąsiednich elementów w posortowanej kolejności. Dlatego każdy certyfikat odrębności zawiera wystarczającą ilość informacji do sortowania, a zatem standardowa dolna granica teoretycznej informacji do sortowania dotyczy również każdego algorytmu deterministycznej odrębności.

— Warren Schudy
źródło

Ten argument działa dla drzew porównawczych, ale nie (bezpośrednio) dla bardziej ogólnych modeli drzew decyzyjnych.

— Jeffε

JeffE: Zgadzam się. Wątpię, aby istniał wystarczająco prosty dowód dla celów Magnusa, który działa w bardziej ogólnym modelu.

— Warren Schudy,

Dobrze. Drzewa porównania są odpowiednie dla mojej aplikacji - więc wydaje mi się, że jest to dość zbliżone do tego, czego szukam. Moja aplikacja wyjaśniała ideę proofów twardości, w tym redukcję do sortowania, więc fakt, że dowód sortowania jest tutaj użyty, w pewnym sensie zwiera całość. Chyba powinienem to wyraźnie powiedzieć :-)

— Magnus Lie Hetland

Nie jestem pewien, czy dobrze rozumiem pytanie, ale udowodnienie przez Dobkina i Liptona [DL79], że problem unikalności liczb n wymaga porównań Ω ( n log n ) w modelu liniowego drzewa decyzyjnego, jest znacznie łatwiejszy niż silniejszy wynik w model drzewa obliczeń algebraicznych Ben-Or [Ben83] (nic dziwnego).

Bibliografia

[Ben83] Michael Ben-Or. Dolne granice dla drzew obliczeń algebraicznych. W Proceedings of the XV rocznego ACM Symposium on Theory of Computing (stoc 1983) , str. 80-86, kwiecień 1983. http://doi.acm.org/10.1145/800061.808735

[DL79] David P. Dobkin i Richard J. Lipton. O złożoności obliczeń w różnych zestawach prymitywów. Journal of Computer and System Sciences , 18 (1): 86–91, lutego 1979 r. Http://dx.doi.org/10.1016/0022-0000(79)90054-0

— Tsuyoshi Ito
źródło

W skrócie: Rozważ przestrzeń R ^ n wszystkich możliwych danych wejściowych. Zestaw dodatnich danych wejściowych ma n! połączone komponenty, po jednym dla każdej permutacji. Z drugiej strony, podzbiory danych wejściowych, które mogą dotrzeć do dowolnego liścia w liniowym drzewie decyzyjnym, są wypukłe i dlatego są połączone. Zatem każde liniowe drzewo decyzyjne, które określa wyjątkowość, ma co najmniej n! pozostawia.

— Jeffε

Bardziej subtelny argument jest wymagany w szczególnym przypadku liczb całkowitych. Patrz Lubiw i Rács, „Dolna granica dla problemu odrębności elementów całkowitych”, Information and Computation 1991; lub Yao, „Dolne granice dla drzew obliczeń algebraicznych z wejściowymi liczbami całkowitymi”, FOCS 1989.

— Jeffε

@JeffE: Twoje krótkie wyjaśnienie jest wspaniałe. Dziękuję również za wskaźnik do interesujących wyników. Nigdy nie przyszło mi do głowy, że dolna granica Ben-Or nie ma natychmiastowego zastosowania w przypadku, gdy dane wejściowe są ograniczone do liczb całkowitych!

— Tsuyoshi Ito,

Jeff: powinny być w odpowiedzi!

— Suresh Venkat

Dzięki zarówno Tsuyoshi Ito, jak i JeffE. Wcześniej widziałem dowód na spację R ^ n (w ustawieniu wykorzystującym argumenty przeciwne). Kiedy po raz pierwszy ją przeczytałem, pomyślałem, że jest to zbyt skomplikowane dla mojej grupy docelowej, ale chyba tak nie jest. Dzięki. (Widziałem też artykuł na temat liczb całkowitych - myślę, że nie będę wchodził w to w swoim wykładzie… :)

— Magnus Lie Hetland