Jak ocenić, czy definicja złożoności obliczeniowej rzeczywistych jest naturalna czy odpowiednia?

Jak wiemy, definicja złożoności obliczeniowej algorytmu prawie nie budzi kontrowersji, ale definicja złożoności obliczeniowej rzeczywistych lub modeli obliczeniowych rzeczywistych nie jest w takim przypadku. Model i model Bluma i Smalesa znamy w książce Computable Analysis. I pozornie model w analizie obliczeniowej jest zgodny z modelem klasycznym, ale definicja złożoności obliczeniowej rzeczywistych nie może zostać przeszczepiona na model klasyczny.

A jak przeszczepić definicję złożoności obliczeniowej rzeczywistych do klasycznego modelu?

— XL _At_Here_There
źródło

W przypadku pierwszego pytania „naturalne” jest pojęciem bardzo subiektywnym i w zależności od osoby, o którą pytasz, jedna lub druga definicja zostanie uznana za najbardziej naturalną. Jeśli chodzi o „odpowiedni”, to zależy: model BSS wydaje się odpowiedni do geometrii obliczeniowej lub obliczeniowej geometrii algebraicznej, a model w analizie obliczeniowej jest bardziej odpowiedni do ... analizy obliczeniowej! Nie rozumiem drugiego pytania.

— Bruno,

@Bruno, dziękuję za komentarz, myślę, że model w analizie obliczeniowej i nie wiem, jak zastosować definicję złożoności obliczeniowej do obliczania liczby rzeczywistej w stosunku do klasycznego modelu, takiego jak Turing Machine, ponieważ złożoność obliczeniowa liczby rzeczywistej w stosunku do modelu w analizie obliczeniowej zależy od jej reprezentacji, a mianowicie danych wejściowych do jej obliczenia.

— XL _At_Here_There

Wydaje ci się, że istnieje pojęcie złożoności obliczania liczb rzeczywistych, które jest niezależne od przedstawienia rzeczywistych liczb. Co sprawia, że tak myślisz? Nie dotyczy to również klasycznej złożoności. Ma to znaczenie, czy masz taśmę, czy pamięć RAM, ma znaczenie, czy reprezentujesz wykresy według list adjancency, macierzy 01 itp.

— Andrej Bauer,

Ale nie jest prawdą, że złożoność nie zależy od reprezentacji. Przechodząc do głupiej reprezentacji, zawsze możesz zrujnować złożoność algorytmu. Pytanie, które należy zadać, brzmi: „Jaka jest dobra reprezentacja danych wejściowych?” W przypadku problemów dyskretnych odpowiedź jest o wiele łatwiejsza niż w przypadku liczb rzeczywistych, ponieważ dobrze rozumie się, co to znaczy „nie marnować bitów”.

— Andrej Bauer,

model BSS wydaje się odpowiedni dla geometrii obliczeniowej - patrz moja odpowiedź na powiązane pytanie . Model Real RAM używany przez geometrów obliczeniowych wyprzedza Blum, Shub i Smale o prawie dekadę.

— Jeffε

Odpowiedzi:

Nie jestem do końca pewien, o co tu chodzi, ale mogę spróbować powiedzieć coś, aby usunąć ewentualne nieporozumienia.

Przede wszystkim, jeśli mówimy o złożoności mapy , nie ma sensu pytać „Co to jest dobra reprezentacja dla $f : \mathbb{R} \to \mathbb{R}$ ? ”Zamiast tego musisz zapytać„ Jaka jest dobra reprezentacja dlawszystkichdanych wejściowych? ”. Porównaj sytuację z łatwiejszą w dyskretnej matematyce: kiedy dyskutujesz o algorytmie, który przyjmuje wykres jako dane wejściowe, nie zapytaj „Czy powinniśmy przedstawiać wykres Petersena jako listę adjancency czy jako macierz binarną?”, ale zamiast tego automatycznie myślisz ojednolitejreprezentacji, która będzie działać dla wszystkich wykresów. $\sqrt{2}$ $f$

Kolejne słowo ostrzeżenia. Zmieniając reprezentację danych wejściowych, zawsze możemy sprawić, że każdy problem (w tym nieobliczalny) będzie trywialnie obliczalny: aby obliczalny, reprezentuj elementy jako pary . Następnie możesz „obliczyć” na podstawie drugiej projekcji. To pokazuje, że potrzebujemy jasnych kryteriów co do reprezentowania danych. $f : A \to B$ $A$ $(a, f(a))$ $f$

Pisałem wielokrotnie o tym, co trzeba, aby reprezentować elementy . Odpowiedź zależy od tego, co struktura z próbujesz przechwytywania. Jeśli próbujesz uchwycić brak struktury, możesz na przykład przedstawić wszystkie rzeczywiste puste listy. Rozsądną listą warunków dla przedstawienia jest to, że musi on być taki, aby: $\mathbb{R}$ $\mathbb{R}$ $\mathbb{R}$

Operacje arytmetyczne , , , są obliczalne, a także wartość bezwzględna . $+$ $\times$ $-$ $/$ $|{-}|$
Istnieje program, który pobiera (reprezentację) rzeczywistego i i wypisuje liczby całkowite takie, że , tzn. Możliwe jest obliczenie dowolnie dobrych racjonalnych przybliżeń. $x$ $k \in \mathbb{N}$ $p, q$ $|x - p/q| \leq 2^{-k}$
Jest to program, który zajmuje (reprezentacje) liczb rzeczywistych i i kończy się wtedy i tylko wtedy, gdy , czyli ścisły rozkaz jest semidecidable. $x$ $y$ $x < y$
Biorąc pod uwagę ciąg (reprezentacji) taki, że reprezentacją wartości granicznej może być obliczona. $(x_n)_n$ $|x_{n+1} - x_n| \leq 2^{-n}$ $\lim_n x_n$

Istnieją stare twierdzenia (patrz referencje do tego artykułu ), które wyjaśniają, dlaczego te warunki są prawidłowe. Twierdzenia te pokazują również, że dowolne dwa takie przedstawienia rzeczywistości są obliczalnie izomorficzne, to znaczy, że możemy je tłumaczyć za pomocą programów. To ustanawia pewne kryteria poprawności, które wyrzucają błędne pomysły.

Na przykład słyszę, jak ludzie mówią takie rzeczy, jak: „liczby wymierne mogą być reprezentowane przez skończoną informację, więc użyjmy tego dla liczb wymiernych, a liczby niewymierne będą musiały być reprezentowane przez nieskończoną informację”. Ten rodzaj rzeczy nie działa, ponieważ łamie czwarty warunek powyżej (rozważ limit liczb niewymiernych - jak możesz powiedzieć, że jest zbieżny z wymiernym?).

Kolejnym przykładem, który powyższe warunki eliminują, jest model Blum-Shub-Smale, ponieważ nie można w nim obliczyć granic sekwencji. Lepiej powiedzieć, że model BSS działa na dyskretnie uporządkowanym podpolu rzeczywistych (generowanych przez dowolne parametry, które występują), a nie na samych rzeczywistych.

Niektóre z poprawnych reprezentacji liczb rzeczywistych są bardziej wydajne niż inne, chociaż jest to nieco trudny temat do dyskusji, ponieważ liczby rzeczywiste są obiektami nieskończonymi. Matthias Schröder zwrócił uwagę, że dla rozsądnej teorii złożoności należy zwrócić uwagę na topologiczne właściwości przedstawienia.

Wreszcie, jak powinniśmy zmierzyć złożoność mapy , zakładając, że mamy dobrą reprezentację ? Ponieważ jest reprezentowane przez funkcję lub nieskończony strumień informacji, lub niektóre z nich, powinniśmy stosować jedno z bardziej złożonych pojęć złożoności . Który prawdopodobnie zależy od reprezentacji, której używasz. $f : \mathbb{R} \to \mathbb{R}$ $\mathbb{R}$ $x \in \mathbb{R}$

Model BSS jest również rozsądnym modelem złożoności obwodu, w którym liczymy operacje arytmetyczne. Warto pamiętać, że w tym modelu nie chodzi o liczby rzeczywiste, ale o coś innego.

— Andrej Bauer
źródło

Dziękuję bardzo za odpowiedź i tak wiele referencji. Czuję się nieswojo w związku z niektórymi pojęciami złożoności obliczeniowej, pozwólcie mi przeczytać odniesienie i zastanowić się przez jakiś czas oraz podać przykład, jeśli znajdę odpowiedni, aby wyjaśnić, dlaczego czuję się tak nieswojo (brzmi to zabawnie, ale moje doświadczenie mówi mi jeśli czuję się niekomfortowo, musi być coś osobliwego)

— XL _At_Here_There

Z mojego doświadczenia czuję się nieswojo z powodu nowej wiedzy, co jest dobrym znakiem i zwykle jest warunkiem wstępnym oświecenia.

— András Salamon

$<_{k}$ $O(t)$ $O(t)$ $O(t)$ $O(t^{2}log(t)log(log(t)))$ . Jak wskazano, rozważania topologiczne są użyteczne, nie wiadomo, czy istnieje jakiś kontekst topologiczny dla tego modelu obliczeń, który pozwala na rzeczywiste obliczenia, które mają niepewność co do precyzji.

— użytkownik3483902
źródło

Czy możesz podać jakieś odniesienie do wykonalnego modelu pamięci RAM?

— XL _At_Here_There

Patrz wyżej w obszarze „... to odniesienie stwierdza ...” zawiera link do artykułu.

— user3483902

Dzięki za zwrócenie uwagi na pracę Brattka & Hertling, już o tym wspomniałem. Chciałbym tylko zauważyć, że model wykonalnej pamięci RAM nie zawiera żadnych funkcji wyższego rzędu, w szczególności nie może obliczyć limitu (szybkiej) sekwencji Cauchy'ego, więc nie liczyłbym tego jako dokładną implementację „rzeczywistych”. Można powiedzieć, że można obliczyć jeden limit „na najwyższym poziomie” (patrz część artykułu, w której mówią o racjonalnych przybliżeniach funkcji).

— Andrej Bauer