Jak określa się liczby rzeczywiste w obliczeniach?

27

To może być podstawowe pytanie, ale czytałem i próbowałem zrozumieć artykuły na takie tematy, jak obliczenia równowagi Nasha i liniowe testy degeneracji, i nie byłem pewien, jak liczby rzeczywiste są określone jako dane wejściowe. Na przykład, kiedy stwierdzono, że LDT ma pewne dolne granice wielomianu, w jaki sposób określa się liczby rzeczywiste, gdy są one traktowane jako dane wejściowe?

cc.complexity-theory computability na.numerical-analysis computing-over-reals computable-analysis Philip White
źródło

1

Dyskusję możesz znaleźć tutaj: en.wikipedia.org/wiki/Computable_number

Joseph Malkevitch

Ktoś powinien złożyć te dokumenty w bezpłatny e-book do pobrania.

Dilawar

34

Nie zgadzam się z Twoją zaakceptowaną odpowiedzią Kaveha. W przypadku programowania liniowego i równowagi Nasha zmiennoprzecinkowa może być dopuszczalna. Ale liczby zmiennoprzecinkowe i geometria obliczeniowa bardzo źle się mieszają: błąd zaokrąglenia unieważnia kombinatoryjne założenia algorytmów, często powodując ich awarię. Mówiąc dokładniej, wiele algorytmów obliczeniowej geometrii zależy od prymitywnych testów, które sprawdzają, czy dana wartość jest dodatnia, ujemna lub zerowa. Jeśli ta wartość jest bardzo bliska zeru, a zaokrąglenie zmiennoprzecinkowe powoduje, że ma zły znak, mogą się zdarzyć złe rzeczy.

Zamiast tego przyjmuje się, że dane wejściowe często mają współrzędne całkowite, a wyniki pośrednie są często przedstawiane dokładnie jako liczby wymierne z wystarczająco dużą dokładnością, aby uniknąć przepełnienia, lub jako liczby algebraiczne. Przybliżenia zmiennoprzecinkowe do tych liczb można wykorzystać do przyspieszenia obliczeń, ale tylko w sytuacjach, w których można zagwarantować, że liczby będą wystarczająco daleko od zera, aby testy znakowe dały prawidłowe odpowiedzi.

W większości prac dotyczących algorytmów teoretycznych w geometrii obliczeniowej problem ten jest pomijany przy założeniu, że dane wejściowe są dokładnymi liczbami rzeczywistymi i że prymitywy są dokładnymi testami znaków pierwiastków wielomianów niskiego stopnia w wartościach wejściowych. Ale jeśli wdrażasz algorytmy geometryczne, to wszystko staje się bardzo ważne.

David Eppstein
źródło

Podobała mi się część odpowiedzi Kaveha, w której zasugerował, że istnieją alternatywne modele obliczeń, ponieważ wydawało się to zgodne z tym, co przeczytałem w artykule, na który patrzyłem. To powiedziawszy, tak naprawdę nie znałem odpowiedzi ... Na razie nie zaakceptowałem odpowiedzi Kaveha. Podejrzewałem, że liczby algebraiczne mogą mieć z tym coś wspólnego. W każdym razie dziękuję za poświęcenie czasu na zastanowienie się nad moim pytaniem ... Zastanowię się i przeczytam dalej, zanim zaakceptuję odpowiedź.

Philip White,

Nie powiedziałem, że jest to dobry model dla CG, miałem na myśli, że nawet gdy autorzy twierdzą, że dane wejściowe są liczbami rzeczywistymi, to nie są to liczby rzeczywiste . Zgadzam się z tobą, że nie powinienem był uwzględniać CG wśród innych. Czytałem bardzo małą liczbę artykułów CG, czy model BSS ma ugruntowaną pozycję w teoretycznych artykułach CG?

Kaveh

1

Przepraszam za moją ignorancję, ale co oznacza BSS?

Philip White,

1

Model BSS jest modelem teoretycznym, który zakłada, że dostępne są dowolne liczby rzeczywiste. To, co zostało zrobione w CG, obejmuje rzeczywiste implementacje modelu, który jest zasadniczo ograniczony do liczb algebraicznych. Również wdrożenia CG są dalekie od kosztu jednostkowego na operację. Więc to nie to samo. Zobacz np. Model rzeczywistej liczby LEDA, citeseerx.ist.psu.edu/viewdoc/...

David Eppstein

10

S

$S$

T

$T$

\sum_{s \in S} \sqrt{s} > \sum_{t \in T} \sqrt{t}

$\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$

15

Możesz także rzucić okiem na wykład Andreja Bauera na temat roli domeny interwałowej we współczesnej rzeczywistej arytmetyki rzeczywistej , który analizuje niektóre z różnych podejść do określania obliczeń na liczbach rzeczywistych zarówno w teorii, jak i praktyce.

Noam Zeilberger
źródło

8

To nie jest bezpośrednia odpowiedź na twoje pytanie, a raczej odpowiedź na Rafaela . Ostatnio sporo pracy określono przy użyciu obliczeń rzeczywistych. Oto kilka artykułów na ten temat.

Koindukcja dla dokładnego obliczania liczb rzeczywistych , Ulrich Berger i Tie Hou: TEORIA SYSTEMÓW OBLICZENIOWYCH Tom 43, Numery 3-4, 394-409, DOI: 10.1007 / s00224-007-9017-6
Koindukcyjne formalne rozumowanie w dokładnej prawdziwej arytmetyki , Milad Niqui, Logical Methods in Computer Science, 4 (3: 6): 1–40, 2008.
Calculus in Coinductive Form autorstwa Dusko Pavlovica i Martina Escardo, LICS 1998.

Nie obejmują one pełnego spektrum obliczeń liczb rzeczywistych, ale poczyniono postępy w rozwiązywaniu różnych problemów.

Dave Clarke
źródło

1

R

$\mathbb{R}$

Słuszna uwaga. Nie jestem pewien, jakie są ograniczenia podejścia koindukcyjnego. Podejście jest w powijakach.

Dave Clarke,

7

Blum, Cucker, Shub i Smale rozważają złożoność obliczeniową obliczeń w stosunku do liczb rzeczywistych . Oto częściowy opis książki:

Klasyczna teoria obliczeń ma swoje początki w pracach Goedela, Turinga, Churcha i Kleene i stanowi niezwykle udane ramy dla teoretycznej informatyki. Teza tej książki jest jednak taka, że stanowi ona niewystarczającą podstawę dla współczesnych obliczeń naukowych, w których większość algorytmów to algorytmy liczb rzeczywistych. Celem tej książki jest opracowanie formalnej teorii obliczeń, która integrowałaby główne tematy teorii klasycznej i która miałaby bardziej bezpośrednie zastosowanie do problemów w matematyce, analizie numerycznej i obliczeniach naukowych. Po drodze autorzy biorą pod uwagę takie fundamentalne problemy, jak: Czy można ustalić, czy zestaw Mandelbrota jest rozstrzygalny? Czy w przypadku prostych map kwadratowych Julia jest zestawem zatrzymującym? Jaka jest prawdziwa złożoność Newtona? metoda s Czy istnieje algorytm decydujący o problemie z plecakiem w wielomianowej liczbie kroków? Czy Hilbert Nullstellensatz jest trudny do rozwiązania? Czy problem znalezienia prawdziwego zera wielomianu stopnia czwartego jest nierozwiązywalny? Czy programowanie liniowe jest realne w realiach?

Recenzję tej książki możesz znaleźć w ACM SIGACT News .

MS Dousti
źródło

Ta książka wygląda bardzo interesująco, dziękuję.

Philip White,

Nie ma za co.

MS Dousti,

5

Warto zauważyć, że model obliczeniowy BSS w odniesieniu do rzeczywistości jest kontrowersyjny z powodów podobnych do tego, o czym wspomniał David Eppstein w powyższym komentarzu. Na przykład: aksjomat BSS obliczający, czy x <y ma jeden krok czasowy, dla dowolnych liczb rzeczywistych x i y. W przeciwieństwie do tego, podejścia takie jak Efektywność typu drugiego (TTE) definiują maszyny, które przyjmują jako przybliżenia wejściowe liczby rzeczywiste i wysyłają przybliżone obliczenia funkcji względem wartości rzeczywistych. Im więcej czasu upłynie, tym lepsze mogą być aproksymacje wejściowe i wyjściowe. Takie podejście wydaje mi się bardziej realistyczne.

Aaron Sterling

@Aaron Sterling: czy znasz dobre referencje dotyczące efektywności typu drugiego?

Joshua Grochow

3

@Joshua Grochow: Przepraszam, że nie dotarłem do tego wcześniej. Książka, do której nawiązuje Kaveh, to „Nielsen and Chuang” z TTE. Jest jednak tak obciążony notacją, że zwykły czytelnik wydawałby się tajemny. Zamiast tego zasugerowałbym następujące slajdy instruktażowe Vasco Brattki: cca-net.de/vasco/cca/tutorial.pdf

Aaron Sterling

7

Edytowane / poprawione na podstawie komentarzy

Kiedy autorzy mówią o wprowadzaniu liczb rzeczywistych w programowaniu liniowym, obliczeniach równowagi Nasha, ... w większości artykułów (prace, które nie dotyczą obliczeń / złożoności w stosunku do liczb rzeczywistych), tak naprawdę nie oznaczają liczb rzeczywistych. Są to liczby wymierne i liczby, które powstają z nich w wyniku ich manipulacji (liczby algebraiczne). Możesz więc myśleć o nich jako o skończonych ciągach.

Z drugiej strony, jeśli artykuł dotyczy obliczalności i złożoności w analizie , to nie używają zwykłego modelu obliczeń, a istnieją różne niekompatybilne modele obliczeń / złożoności w stosunku do liczb rzeczywistych.

Jeśli artykuł nie określa modelu obliczeń na liczbach rzeczywistych, można bezpiecznie założyć, że jest to pierwszy przypadek, tzn. Są to tylko liczby wymierne.

Geometria obliczeniowa jest inna. W większości artykułów w CG, jeśli autorzy nie określają, jaki jest model, który w odniesieniu do niego omawia poprawność i złożoność algorytmu, można założyć, że jest to model BSS (inaczej RAM-real).

Model nie jest realistyczny i dlatego wdrożenie nie jest proste. (Jest to jeden z powodów, dla których niektórzy ludzie w CCA preferują modele teoretyczne Ko-Friedmana / TTE / Domain , ale problem z tymi modelami polega na tym, że nie są one tak szybkie jak obliczenia zmiennoprzecinkowe w praktyce.) Poprawność i złożoność algorytm w modelu BSS niekoniecznie przechodzi na poprawność zaimplementowanego algorytmu.

Książka Weihraucha zawiera porównanie różnych modeli (rozdział 9.8). To tylko trzy strony i warto je przeczytać.

(Istnieje również trzeci sposób, który może być bardziej odpowiedni dla CG, możesz rzucić okiem na ten artykuł:

Chee Yap, „ Teoria rzeczywistych obliczeń według EGC ”

gdzie EGC to dokładne obliczenie geometryczne ).

Kaveh
źródło

Myślę, że artykuł, który przede wszystkim mnie interesuje, określa model, ponieważ zawiera zdanie: „Formalnie definiujemy teraz nasz model obliczeń”. Artykuł nazywa się „Dolnymi granicami problemów satysfakcji” i wydaje się, że istnieje dyskusja na temat liniowych drzew decyzyjnych i wielomianów zapytań. Myślę, że to była odpowiedź, której tam szukałem ... dzięki. Przeczytam ponownie artykuł i zobaczę, czy mogę to zrozumieć.

Philip White,

2

Nie zgadzam się. To zły model geometrii obliczeniowej. Zobacz moją bardziej szczegółową odpowiedź poniżej.

David Eppstein,

1

@Kaveh: Myślę, że powinieneś powiedzieć, że są to liczby wymierne , a nie liczby zmiennoprzecinkowe. Dokładne liczby wymierne są łatwe do przedstawienia za pomocą ciągów skończonych, aw wielu aplikacjach (np. Związanych z programowaniem liniowym) wyniki pośrednie będą również liczbami wymiernymi, jeśli dane wejściowe są liczbami wymiernymi. (Oczywiście, jak zauważył David Eppstein, komp. Geom. Jest godnym uwagi wyjątkiem, ponieważ wyniki pośrednie zwykle nie są racjonalne.)

Jukka Suomela,

@Jukka: Masz rację, zamienię zmiennoprzecinkowe na racjonalne.

Kaveh

5

Nie. Kiedy piszę „liczba rzeczywista”, naprawdę mam na myśli „liczbę rzeczywistą”, a przez to mam na myśli naprawdę liczbę rzeczywistą, naprawdę z reali. Naprawdę. W szczególności w artykule na temat @Philip muszę założyć, że algorytmy działają dla dowolnych rzeczywistych danych wejściowych, aby móc zastosować wyniki niestandardowej analizy.

Jeffε,

3

Nie są i ogólnie nie mogą. Z naszymi modelami obliczeń możemy liczyć tylko policzalną liczbę danych wejściowych (oraz danych wyjściowych i funkcji). W szczególności wszelkie dane wejściowe muszą być skończone, ale nie wszystkie liczby rzeczywiste mają skończone reprezentacje.

Sądzę, że można założyć jakąś wyrocznię, która na żądanie daje następną cyfrę określonej liczby rzeczywistej (coś jak strumień). W przeciwnym razie będziesz musiał żyć z (dowolnie precyzyjnymi) przybliżeniami.

Raphael
źródło

Jeśli to prawda, w jaki sposób LDT może traktować liczby rzeczywiste? Czytałem coś o „drzewach decyzyjnych r-liniowych”, ale tak naprawdę nie rozumiałem, o czym mówią w artykule „Dolne granice dla problemów liniowej satyfikacji”.

Philip White,

Założę się, że albo nie mogą, albo nie używają maszyn Turinga (lub równoważnych koncepcji). Inne odpowiedzi, które nie są tak ścisłe / ogólne jak moje, powinny rzucić na to nieco światła.

Raphael,

Jak określa się liczby rzeczywiste w obliczeniach?

Odpowiedzi:

Edytowane / poprawione na podstawie komentarzy