Jakie są powody, dla których badacze geometrii obliczeniowej preferują model BSS / real-RAM?

tło

Obliczenia na liczbach rzeczywistych są bardziej skomplikowane niż obliczenia na liczbach naturalnych, ponieważ liczby rzeczywiste są obiektami nieskończonymi i istnieje niezliczona liczba liczb rzeczywistych, dlatego liczb rzeczywistych nie można wiernie przedstawić za pomocą ciągów skończonych nad skończonym alfabetem.

W przeciwieństwie do klasycznego obliczania ciągów skończonych, w którym różne modele obliczeń, takie jak: rachunek lambda, maszyny Turinga, funkcje rekurencyjne ... okazują się równoważne (przynajmniej w przypadku obliczania funkcji na ciągach), istnieją różne proponowane modele obliczeń liczby rzeczywiste, które nie są kompatybilne. Na przykład w modelu TTE (patrz także [Wei00]), który jest najbliższy klasycznemu modelowi maszyny Turinga, liczby rzeczywiste są reprezentowane za pomocą nieskończonych taśm wejściowych (takich jak wyrocznie Turinga) i nie można zdecydować o porównaniu i relacje równości między dwiema danymi liczbami rzeczywistymi (w skończonym czasie). Z drugiej strony w modelach BBS / real-RAM, które są podobne do modelu maszyny RAM, mamy zmienne, które mogą przechowywać dowolne liczby rzeczywiste, a porównania i równość należą do operacji atomowych modelu. Z tego i podobnych powodów wielu ekspertów twierdzi, że modele BSS / rzeczywistej pamięci RAM nie są realistyczne (nie można ich wdrożyć, przynajmniej nie na obecnych komputerach cyfrowych) i wolą TTE lub inne modele równoważne od TTE, takie jak efektywny model teoretyczny domeny, Model Ko-Friedmana itp.

Jeśli dobrze zrozumiałem , domyślnym modelem obliczeń stosowanym w geometrii obliczeniowej jest model BSS (inaczej real-RAM , patrz [BCSS98]).

Z drugiej strony wydaje mi się, że przy implementacji algorytmów w geometrii obliczeniowej (np. LEDA ) mamy do czynienia tylko z liczbami algebraicznymi i nie mamy do czynienia z żadnymi nieskończonymi obiektami lub obliczeniami wyższego typu (czy to prawda?). Tak więc wydaje mi się (prawdopodobnie naiwnie), że można również użyć klasycznego modelu obliczeń na łańcuchach skończonych, aby poradzić sobie z tymi liczbami i użyć zwykłego modelu obliczeń (który jest również używany do implementacji algorytmów) w celu omówienia poprawności i złożoności algorytmów.

Pytania:

Jakie są powody, dla których naukowcy zajmujący się geometrią obliczeniową wolą korzystać z modelu BSS / real-RAM? (powody specyficznej geometrii obliczeniowej dla zastosowania modelu BSS / real-RAM)

Jakie są problemy z (prawdopodobnie naiwnym) pomysłem, o którym wspominałem w poprzednim akapicie? (przy użyciu klasycznego modelu obliczeń i ograniczania danych wejściowych do liczb algebraicznych w geometrii obliczeniowej)

Uzupełnienie:

Istnieje również złożoność problemu algorytmów, bardzo łatwo jest wybrać następujący problem w modelu BSS / real-RAM:

Biorąc pod uwagę dwa zestawy i dodatnich liczb całkowitych, czy ?T ∑ s ∈ S $S$$T$
$\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$

Chociaż nie jest znany żaden skuteczny algorytm całkowitej liczby pamięci RAM do jego rozwiązania. Dzięki JeffE za przykład.

Bibliografia:

1. Lenore Blum, Felipe Cucker, Michael Shub i Stephen Smale, „Complexity and Real Computation”, 1998
2. Klaus Weihrauch, „ Computable Analysis, An Introduction ”, 2000

Po pierwsze, geometrycy obliczeniowi nie uważają tego za model BSS. Prawdziwy model pamięci RAM zdefiniował Michael Shamos w swojej rozprawie doktorskiej z 1978 r. ( Geometria obliczeniowa ), która prawdopodobnie zapoczątkowała tę dziedzinę. Franco Preparata zrewidował i rozszerzył tezę Shamosa do pierwszego podręcznika geometrii obliczeniowej, opublikowanego w 1985 r. Rzeczywista pamięć RAM jest również równoważna ( z wyjątkiem jednolitości; patrz odpowiedź Pascala! ) Z modelem drzewa obliczeń algebraicznych zdefiniowanym przez Ben-Or w 1983 r. Blum , Shub i Smale starały się opublikować w 1989 roku, długo po ustanowieniu prawdziwej pamięci RAM, i zostały prawie całkowicie zignorowane przez społeczność geometrii obliczeniowej.

Większość (klasycznych) wyników w geometrii obliczeniowej jest silnie związana z zagadnieniami w geometrii kombinatorycznej , dla których założenia o współrzędnych będących integralnymi lub algebraicznymi są (co najwyżej) nieistotne. Mówiąc jako rodowity, wydaje się całkowicie naturalne, że arbitralne punkty, linie, okręgi i tym podobne obiekty są pierwszorzędnymi obiektami przy udowadnianiu rzeczy na ich temat, a zatem równie naturalne podczas projektowania i analizy algorytmów do ich obliczenia.

W przypadku większości (klasycznych) algorytmów geometrycznych takie podejście jest uzasadnione nawet w praktyce. Większość algorytmów dla płaskich problemów geometrycznych jest zbudowana na bardzo małej liczbie prymitywów geometrycznych: Czy punkt jest na lewo czy na prawo od punktu ? Powyżej, poniżej lub na linii przechodzącej przez punkty i ? Wewnątrz, na zewnątrz lub na okręgu określonym przez punkty ? Lewy czy prawy od przecięcia segmentów i ? Każda z tych prymitywów jest implementowana poprzez ocenę znaku wielomianu niskiego stopnia we współrzędnych wejściowych. (Więc te algorytmy można opisać w słabszej decyzji algebraicznejq q r q , r , s q r s $p$$q$$q$$r$$q,r,s$$qr$$st$ model drzewa.) Jeśli współrzędne wejściowe są liczbami całkowitymi, te prymitywy można dokładnie oszacować przy jedynie stałym zwiększeniu precyzji, a zatem czasy działania w rzeczywistej pamięci RAM i całkowitej liczbie pamięci RAM są takie same.

Z podobnych powodów, kiedy większość ludzi myśli o algorytmach sortowania, nie przejmuje się tym , co sortuje, o ile dane pochodzą z całkowicie uporządkowanego wszechświata, a dowolne dwie wartości można porównywać w stałym czasie.

Społeczność opracowała więc podział problemów między projektowaniem „rzeczywistych” algorytmów geometrycznych a ich praktyczną implementacją; stąd rozwój pakietów takich jak LEDA i CGAL. Nawet dla osób pracujących nad obliczeniami dokładnymi istnieje rozróżnienie między prawdziwym algorytmem, który wykorzystuje dokładną prawdziwą arytmetykę jako część modelu bazowego, a implementacją , która jest wymuszona przez nieistotne ograniczenia fizycznych urządzeń komputerowych do korzystania z obliczeń dyskretnych.

Na przykład w tym światopoglądzie najważniejszym otwartym problemem w geometrii obliczeniowej jest istnienie algorytmu wielomianowego dla programowania liniowego. Nie, metody elipsoidy i punktu wewnętrznego nie liczą się. W przeciwieństwie do algorytmu simpleks, nie gwarantuje się, że algorytmy te zakończą się, chyba że macierz ograniczeń będzie racjonalna. ( Istnieją kombinatoryczne typy wypukłych polytopów, które mogą być reprezentowane tylko przez irracjonalne macierze ograniczeń , więc jest to ograniczenie nietrywialne). I nawet gdy macierz ograniczeń jest racjonalna, czasy działania tych algorytmów nie są ograniczone żadną funkcją rozmiar wejściowy (wymiar # ograniczenia).$\times$

Istnieje kilka algorytmów geometrycznych, które naprawdę w dużym stopniu opierają się na modelu drzewa obliczeń algebraicznych , a zatem nie można ich dokładnie i skutecznie zaimplementować na komputerach fizycznych. Dobrym przykładem są ścieżki minimalnego łącza w prostych wielokątach, które mogą być obliczone w czasie liniowym na prawdziwej pamięci RAM, ale wymagają kwadratowej liczby bitów w najgorszym przypadku do dokładnego przedstawienia. Innym dobrym przykładem są hierarchiczne wycinki Chazelle , które są wykorzystywane w najbardziej wydajnych algorytmach znanych z wyszukiwania zasięgu simpleks. Te sadzonki używają hierarchii zbiorów trójkątów, w których wierzchołki trójkątów na każdym poziomie są punktami przecięcia linii przez krawędzie trójkątów na poprzednich poziomach. Zatem nawet jeśli współrzędne wejściowe są liczbami całkowitymi, współrzędne wierzchołków dla tych trójkątów są liczbami algebraicznymi o nieograniczonym stopniu; niemniej jednak algorytmy konstruowania i stosowania wycinków zakładają, że współrzędnymi można manipulować dokładnie w stałym czasie.

Tak więc moja krótka, osobista uprzedzenie odpowiedź brzmi: TTE, teoria domen, Ko-Friedman i inne modele „realistycznych” obliczeń w liczbach rzeczywistych rozwiązują wszystkie problemy, na które społeczność geometrii obliczeniowej w ogóle się nie przejmuje .

Nie jest do końca prawdą, że prawdziwy model RAM / BSS jest równoważny modelowi drzewa obliczeń algebraicznych. To drugie jest bardziej wydajne, ponieważ wielomianowe drzewo głębokości może mieć wykładniczy rozmiar. Daje to dużo miejsca na kodowanie niejednorodnych informacji. Na przykład Meyer auf der Heide wykazał, że algebraiczne (nawet liniowe) drzewa decyzyjne mogą skutecznie rozwiązywać trudne problemy, takie jak suma podzbiorów, ale jest to (przypuszczalnie) niemożliwe w prawdziwym modelu RAM / BSS.

Oto komentarz do doskonałej odpowiedzi Jeffa:

Zaproponowano pojęcia warunku, aproksymacji i zaokrąglenia w celu rozwiązania luki złożoności (kombinatorycznej vs. ciągłej) algorytmów programowania liniowego. Stan wystąpienia problemu ocenia wpływ niewielkich zakłóceń sygnału wejściowego na dokładność sygnału wyjściowego. Pojęcie warunku zostało po raz pierwszy wprowadzone przez Alana Turinga. Jim Renegar wprowadził pojęcie warunku programu liniowego.

L. Blum obliczeniowe przez Real Gdzie Turinga Spełnia Newton, , zawiadomienia o AMS, tom 51, nr 9 (2004), 1024-1034

A. TURING, Błędy zaokrąglania w procesach macierzowych, Kwart. J. Mech. Appl. Matematyka 1 (1948) 287–308

J. RENEGAR, Włączanie liczb warunków do teorii złożoności programowania liniowego, SIAM J. Optim. 5 (1995) 506–524

F. CUCKER i J. PEÑA, Pierwotny podwójny algorytm do rozwiązywania wielościennych układów stożkowych za pomocą maszyny o skończonej precyzji, SIAM Journal on Optimization 12 (2002), 522–554.