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.

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

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

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ściowychf? ”. 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 A jako pary ( a , f ( a ) ) . Następnie możesz „obliczyć” f 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 R 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 R jest to, że musi on być taki, aby:$\mathbb{R}$$\mathbb{R}$$\mathbb{R}$

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

$<_{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.