Wie kann man die Definition der rechnerischen Komplexität von Real beurteilen, die natürlich oder geeignet ist?

Wie wir wissen, ist die Definition der rechnerischen Komplexität von Algorithmen fast unumstritten, aber die Definition der rechnerischen Komplexität von Real oder der Berechnungsmodelle über Real ist in einem solchen Fall nicht. Wir kennen das Modell und das Modell von Blum und Smales im Buch Computable Analysis. Und anscheinend stimmt das Modell in der berechenbaren Analyse mit dem klassischen Modell überein, aber die Definition der rechnerischen Komplexität von Real kann nicht in das klassische Modell übertragen werden.

Wie kann man die Definition der rechnerischen Komplexität von Real beurteilen, die natürlich oder geeignet ist?

Und wie lässt sich die Definition der rechnerischen Komplexität von Real in ein klassisches Modell übertragen?

Ich bin mir nicht ganz sicher, was die Frage hier ist, aber ich kann versuchen, ein wenig zu sagen, um mögliche Missverständnisse auszuräumen.

$f : \mathbb{R} \to \mathbb{R}$$\sqrt{2}$$f$

$f : A \to B$$A$$(a, f(a))$$f$

$\mathbb{R}$$\mathbb{R}$$\mathbb{R}$

1. $+$$\times$$-$$/$$|{-}|$
2. $x$$k \in \mathbb{N}$$p, q$$|x - p/q| \leq 2^{-k}$
3. $x$$y$$x < y$
4. $(x_n)_n$$|x_{n+1} - x_n| \leq 2^{-n}$$\lim_n x_n$

Es gibt alte Theoreme (siehe Einleitung zu diesem Artikel für Referenzen), die erklären, warum diese Bedingungen die richtigen sind. Diese Theoreme zeigen auch, dass zwei solche Darstellungen von Realen rechnerisch isomorph sind, dh wir können mit Programmen zwischen ihnen übersetzen. Dies legt einige Kriterien für die Korrektheit fest, die fehlerhafte Ideen aufwerfen.

Zum Beispiel höre ich Leute Dinge sagen wie "rationale Zahlen können durch endliche Informationen dargestellt werden, also verwenden wir das für rationale Zahlen, und die irrationalen Zahlen müssen durch unendliche Informationen dargestellt werden". Diese Art von Dingen funktioniert nicht, weil sie die obige vierte Bedingung brechen (betrachten Sie eine Grenze irrationaler Zahlen - wie können Sie feststellen, dass sie zu einer rationalen konvergieren?).

Ein weiteres Beispiel, das durch die obigen Bedingungen beseitigt wird, ist das Blum-Shub-Smale-Modell, da darin keine Sequenzgrenzen berechnet werden können. Es ist besser zu sagen, dass das BSS-Modell auf einem diskreten geordneten Teilfeld von Real (das durch die vorhandenen Parameter erzeugt wird) arbeitet, nicht auf den Real selbst.

Unter den korrekten Darstellungen von Real sind einige effizienter als andere, obwohl dies ein etwas schwierig zu diskutierendes Thema ist, da reelle Zahlen unendliche Objekte sind. Matthias Schröder wies darauf hin, dass man für eine vernünftige Komplexitätstheorie auf die topologischen Eigenschaften der Darstellung achten muss.

Schließlich , wie wir sollten die Komplexität einer Karte messen , vorausgesetzt , sie eine gute Darstellung von dem , ? Da durch eine Funktion oder einen unendlichen Informationsstrom oder einen solchen dargestellt wird, sollten wir einen der komplexeren Begriffe vom höheren Typ verwenden . Welche wahrscheinlich von der verwendeten Darstellung abhängt.$f : \mathbb{R} \to \mathbb{R}$$\mathbb{R}$$x \in \mathbb{R}$

Das BSS-Modell ist auch ein vernünftiges Schaltungskomplexitätsmodell, in dem wir arithmetische Operationen zählen. Es ist nur gut zu bedenken, dass es bei diesem Modell nicht um reelle Zahlen geht, sondern um etwas anderes.

Ein weiteres Modell, das möglicherweise untersucht werden muss, ist das des realisierbaren RAM-Modells. Dies ist ein modifiziertes Real-RAM-Modell für Real-Berechnung, machbares RAM oder ein modifiziertes RAM-Modell, das sowohl die diskreten als auch die reellen arithmetischen Operationen verwendet. Dieses Modell ermöglicht reale und diskrete Operationen, und das Turing-Modell ist damit austauschbar. Das realisierbare RAM-Modell hat eine mit Unsicherheit definierte Genauigkeit, was bedeutet, dass Vergleiche von reellen Zahlen nur bis zu einer variablen Unsicherheit 1 / (k + 1) ermöglicht. Dies ermöglicht ungefähre Berechnungen. Wie Vasco Brattkaa und Peter Hertlingb in Feasible Real Random Access Machines darlegen , sind auch die Modelle von Turing und die von Feasible Real RAMs verwandt. Alle Funktionen, die auf einer Turing-Maschine in der Zeit$<_{k}$$O(t)$sind auf einem RAM in der Zeit berechenbar , und im umgekehrten Fall gibt es einen gewissen Overhead für die Turing-Maschine, die die Funktion berechnet (wenn der reale RAM die Funktion in berechnet, berechnet das TM die Funktion in . Wie bereits erwähnt, sind topologische Überlegungen nützlich. Man weiß nicht, ob für dieses Berechnungsmodell ein topologischer Kontext entwickelt wurde, der reale Berechnungen ermöglicht, die mit Unsicherheit behaftet sind in Präzision.$O(t)$$O(t)$$O(t^{2}log(t)log(log(t)))$