Uzasadnianie naukowcom asymptotycznej analizy najgorszego przypadku

Pracowałem nad wprowadzeniem niektórych wyników złożoności obliczeniowej do biologii teoretycznej, zwłaszcza ewolucji i ekologii , aby być interesującym / użytecznym dla biologów. Jedną z największych trudności, jakie napotkałem, jest uzasadnienie przydatności asymptotycznej analizy najgorszego przypadku dla dolnych granic. Czy istnieją odniesienia do długości artykułów, które uzasadniają dolne granice i asymptotyczną analizę najgorszego przypadku dla odbiorców naukowych?

Naprawdę szukam dobrego odniesienia, do którego mógłbym się odnieść w swoim piśmie, zamiast konieczności przechodzenia przez uzasadnienia w ograniczonej przestrzeni, jaką mam dostępną (ponieważ nie jest to centralny punkt artykułu). Zdaję sobie również sprawę z innych rodzajów i modeli analizy, więc ja nie szukam odniesienia, który mówi najgorszy przypadek jest „najlepszy” analiza (ponieważ istnieją ustawienia kiedy bardzo dużo nie jest), ale że nie jest całkowicie bezużyteczne: wciąż daje nam teoretycznie użyteczny wgląd w zachowanie rzeczywistych algorytmów na rzeczywistych danych wejściowych. Ważne jest również, aby pisanie było skierowane do ogólnych naukowców a nie tylko inżynierowie, matematycy lub informatycy.

Na przykład esej Tima Roughgarden'a przedstawiający ekonomistom teorię złożoności jest na dobrej drodze do tego, czego chcę. Jednak istotne są tylko sekcje 1 i 2 (reszta jest zbyt specyficzna ekonomicznie), a docelowi odbiorcy są nieco bardziej zadowoleni z myślenia odpornego na twierdzenia lematyczne niż większość naukowców ^[1] .

Detale

W kontekście dynamiki adaptacyjnej w ewolucji spotkałem dwa specyficzne typy odporności biologów teoretycznych:

[A] „Dlaczego miałbym przejmować się zachowaniem dla dowolnego ? Wiem już, że genom ma n = 3 ∗ 10 9 par zasad (a może n = 2 ∗ 10 4 genów) i nie więcej.”$n$$n = 3*10^9$$n = 2*10^4$

Jest to stosunkowo łatwe do wytarcia z argumentem „możemy sobie wyobrazić czekanie na sekund, ale nie na 2 10 9 ”. Ale bardziej skomplikowany argument może brzmieć: „jasne, mówisz, że zależy ci tylko na konkretnym n , ale twoje teorie nigdy nie wykorzystują tego faktu, po prostu używają tego, że jest duży, ale skończony, i to jest twoja teoria, z którą studiujemy analiza asymptotyczna ”.$10^9$$2^{10^9}$$n$

[B] „Ale pokazałeś tylko, że budowanie tego specyficznego krajobrazu za pomocą tych gadżetów jest trudne. Dlaczego miałbym się tym przejmować zamiast przeciętnego?”

Jest to trudniejsza krytyka, ponieważ wiele narzędzi powszechnie używanych w tej dziedzinie pochodzi z fizyki statystycznej, w której często bezpiecznie jest założyć jednolity (lub inny konkretny prosty) rozkład. Ale biologia to „fizyka z historią” i prawie wszystko nie jest w równowadze lub „typowe”, a wiedza empiryczna jest niewystarczającauzasadnić założenia dotyczące rozkładów nad danymi wejściowymi. Innymi słowy, chcę argumentu podobnego do argumentu zastosowanego przeciwko jednolitej analizie średnich przypadków w analizie średnich dystrybucji w inżynierii oprogramowania: „modelujemy algorytm, nie możemy skonstruować rozsądnego modelu interakcji użytkownika z algorytmem lub jego dystrybucji wejściowe będą; dotyczy to psychologów lub użytkowników końcowych, a nie nas ”. Z wyjątkiem tego przypadku, nauka nie znajduje się w sytuacji, w której istnieje odpowiednik „psychologów lub użytkowników końcowych”, aby dowiedzieć się, jakie są podstawowe dystrybucje (lub jeśli jest to nawet znaczące).

Uwagi i powiązane pytania

1. Link omawia nauki kognitywne, ale sposób myślenia jest podobny w biologii. Jeśli przejrzysz Evolution lub Journal of Theoretical Biology , rzadko zobaczysz dowód na twierdzenie-lemma, a kiedy to zrobisz, zwykle będzie to tylko obliczenie zamiast czegoś w rodzaju dowodu istnienia lub skomplikowanej konstrukcji.
2. Paradygmaty analizy złożoności algorytmów
3. Inne rodzaje analizy czasu pracy oprócz najgorszego przypadku, średniego przypadku itp.?
4. Ekologia i ewolucja poprzez soczewkę algorytmiczną
5. Dlaczego ekonomiści powinni dbać o złożoność obliczeniową

Moim osobistym (i stronniczym) podejściem jest to, że asymptotyczna analiza najgorszego przypadku jest historycznym krokiem w kierunku bardziej praktycznych analiz. Dlatego wydaje się trudne do uzasadnienia dla praktyków.

Ustalenie granic dla najgorszego przypadku jest często łatwiejsze niż udowodnienie granic nawet dla „ładnych” definicji przeciętnego przypadku. Analiza asymptotyczna jest również często o wiele łatwiejsza niż wykazanie dość ciasnych granic. Dlatego analiza asymptotyczna w najgorszym przypadku jest doskonałym miejscem na rozpoczęcie.

Praca Daniela Spielmana i Shanghua Tenga nad płynną analizą Simplex wydaje mi się zwiastunem tego, co może się zdarzyć, gdy zaczniemy lepiej rozumieć kształt problemu: najpierw zajęcie się najgorszym przypadkiem pozwala na bardziej precyzyjne zrozumienie rozwinięty. Co więcej, jak zasugerował Aaron Roth w komentarzach, jeśli „zwykłe” zachowanie systemu znacznie różni się od jego najgorszego przypadku, to system nie jest jeszcze w pełni określony i potrzeba więcej pracy, aby ulepszyć model. Zatem wyjście poza najgorszy przypadek na ogół wydaje się ważne jako cel długoterminowy.

Jeśli chodzi o analizę asymptotyczną, zwykle służy ona do trzymania długiego i niechlujnego dowodu z dala od rozpraszających szczegółów. Niestety, obecnie wydaje się, że nie ma sposobu na nagrodzenie żmudnej pracy polegającej na wypełnianiu szczegółów w celu uzyskania rzeczywistych stałych, tak że rzadko wydaje się, że jest to zrobione. (Ograniczenia strony również działają przeciwko temu.) Staranna analiza szczegółów asymptotycznej granicy doprowadziła do faktycznych algorytmów, z dobrymi granicami stałych, więc osobiście chciałbym zobaczyć więcej tego rodzaju pracy. Być może jeśli sformalizowanych zostanie więcej dowodów za pomocą systemów asystenta dowodów, wówczas stałe można oszacować przy mniejszym wysiłku. (Lub granice stałych, zgodnie z linią Gowersa związaną z Szemerédi Regularity Lemma, mogą stać się bardziej rutynowe.) Istnieją również sposoby udowodnienia dolnych granic, które są wolne od stałych, za pomocą bardziej wyraźnych modeli maszyn (takich jak deterministyczne automaty skończone). Jednak takie (prawie) dokładne dolne granice dla bardziej ogólnych modeli obliczeń mogą wymagać dużo pracy lub być całkowicie poza zasięgiem. Wydaje się, że zostało to zrealizowane w latach ~ 1958–73 podczas pierwszego rozkwitu teorii automatów, ale o ile wiem, w dużej mierze pozostawiono je w spokoju.

$O$$(n^k)$

Dolne granice i analiza najgorszego przypadku zwykle nie idą w parze. Nie twierdzisz, że algorytm zajmie co najmniej wykładniczy czas w najgorszym przypadku, dlatego jest zły. Mówisz, że w najgorszym przypadku może to zająć maksymalnie czas liniowy, a zatem jest dobre. Ten pierwszy jest użyteczny tylko wtedy, gdy zamierzasz uruchomić algorytm na wszystkich możliwych wejściach, a nie tylko na średnich danych wejściowych.

Jeśli chcesz użyć dolnych granic w celu wykazania złości, potrzebujesz analizy najlepszych przypadków lub analizy średnich przypadków. Możesz uprościć te rzeczy, opierając się na stwierdzeniu @ PeterShor, że najgorsze i średnie są często bardzo podobne, i podaje listę prania algorytmów, dla których jest to prawdą. (Np .: wszystkie klasyczne rodzaje oprócz szybkiego sortowania.)

Jeśli chodzi o wykazanie, że asymptotyki mają znaczenie w porównaniu ze stałymi danymi wejściowymi i stałymi czynnikami, moim ulubionym artykułem na ten temat jest „Perły programowania: techniki projektowania algorytmów” Jona Bentleya. Przedstawia cztery różne rozwiązania prostego problemu macierzowego i pokazuje, w jaki sposób podejście liniowe unicestwia podejście sześcienne. Swoją tabelę nazywa „Tyranią Asymptotyków”, po tym, jak fizycy używali terminu „równanie rakiety”. Korzystam z tego przykładu, aby motywować do poszukiwania lepszych algorytmów studentom w wieku przedszkolnym.

Czy nie-informatyk zapozna się z artykułem zawierającym kod i będzie wiedział, jak pominąć szczegóły niskiego poziomu, aby uzyskać ogólny obraz? Nie wiem Być może gdzieś jest lepsza prezentacja. Ale myślę, że jest to przyzwoity zasób do cytowania.

A jeśli twierdzą, że nie dbają o arbitralnie duże n, niech uruchomią rekurencyjne niezapamiętywane Fibonacciego na 3 * 10 ⁹ parach zasad i powiedz im, że to O (1), ponieważ wielkość sekwencji DNA jest ustalona. ;)

wielu zgodziło się, że jest to ważny temat do zbadania / omówienia, ale wydaje się, że nie było to jeszcze wiele. kilka bibl o różnym stylu / WYDAJNOŚĆ / widzów / formalności nie dokładnie zgodnie z wnioskiem, ale raczej blisko (najlepiej widoczne w Internecie do tej pory na średnim wyszukiwania, nadzieję usłyszeć dodatkowo żadnej lepszych; więcej uwagi poniżej):

• Złożoność algorytmów Atkinsona (niestety tylko jeden odnośnik do biologii w artykule, ale może wystarczyć na bardziej ogólnych terminach nauki / inżynierii)

  Współczesna teoria algorytmów pochodzi z późnych lat 60. XX wieku, kiedy zaczęto stosować metodę asymptotycznego pomiaru czasu wykonania. Argumentuje się, że przedmiot ma zarówno skrzydła inżynierskie, jak i naukowe. Skrzydło inżynierskie składa się z dobrze zrozumiałych metodologii projektowania, podczas gdy skrzydło naukowe zajmuje się podstawami teoretycznymi. Kluczowe problemy obu skrzydeł są badane. Na koniec podaje się kilka osobistych opinii na temat tego, gdzie temat pójdzie dalej.

• Złożoność i algorytmy J. Diaz. 100 slajdów. szeroki; można w szczególności wyciąć odpowiednie.

• Delikatne wprowadzenie do analizy złożoności algorytmów Dioniza „dionyziz” Zindros

innymi słowy, czy istnieje coś w rodzaju wstępu / badania / przeglądu soczewki teoretycznej złożoności w ścisłej kombinacji / koniunkcji / towarzysza z postępującą soczewką algorytmiczną w nauce, coś w rodzaju „teorii złożoności dla naukowców, inżynierów i badaczy” ?

istnieją dobre referencje na temat poprzedniej „soczewki algorytmicznej”, którą zacytowałeś, np. Papadimitriou, ale nie wydaje się, aby wysoce zadowalająca referencja od eksperta w tej dziedzinie została napisana na tej ostatniej „soczewce złożoności”… jeszcze (może niektóre „elitarne” „ członek tej witryny uzna to za następny projekt książkowy lub papierowy).

należy również zauważyć, że istnieje wiele odniesień do trafności P w porównaniu do NP poza teorią złożoności oraz w innych dziedzinach naukowych, które można by w pewnym stopniu wykorzystać do tych celów. doda je w komentarzach, jeśli będzie jakieś zainteresowanie.