Comment juger que la définition de la complexité de calcul des réels est naturelle ou appropriée?

Comme nous le savons, la définition de la complexité de calcul de l'algorithme est presque sans controverse, mais la définition de la complexité de calcul des réels ou des modèles de calcul sur les réels n'est pas dans un tel cas. Nous connaissons le modèle et le modèle de Blum et Smales dans le livre Computable Analysis. Et apparemment, le modèle dans l'analyse calculable est cohérent avec le modèle classique, mais la définition de la complexité de calcul des réels ne peut pas être transplantée dans le modèle classique.

Et comment transplanter la définition de la complexité de calcul des réels dans le modèle classique?

cc.complexity-theory reference-request computability computing-over-reals computable-analysis XL _At_Here_There
la source

Pour votre première question, «naturel» est une notion très subjective et selon la personne à qui vous posez la question, l'une ou l'autre définition sera considérée comme la plus naturelle. Quant à «convenable», cela dépend: le modèle BSS semble convenir à la géométrie computationnelle ou à la géométrie algébrique computationnelle, et le modèle en analyse calculable est plus adapté à ... l'analyse calculable! Je ne comprends pas la deuxième question.

Bruno

@Bruno, merci pour votre commentaire, je pense que le modèle en analyse calculable, et je ne sais pas comment appliquer la définition de la complexité de calcul au calcul du nombre réel sur un modèle classique comme Turing Machine, car la complexité de calcul du nombre réel sur le modèle en analyse calculable dépend de la représentation de celui-ci, à savoir, l'entrée pour le calcul de celui-ci.

XL _At_Here_There

Vous semblez penser qu'il existe une notion de complexité pour le calcul des nombres réels qui est indépendante de la représentation des réels. Qu'est-ce qui vous fait penser cela? Ce n'est pas le cas non plus dans la complexité classique. Peu importe que vous ayez une bande ou une machine RAM, que vous représentiez des graphiques par des listes d'adjonction ou des matrices 01, etc.

Andrej Bauer

Mais ce n'est pas vrai que la complexité ne dépend pas de la représentation. En passant à une représentation stupide, vous pouvez toujours ruiner la complexité d'un algorithme. La question à poser est: "Qu'est-ce qu'une bonne représentation de l'entrée?" Pour les problèmes discrets, il est beaucoup plus facile de répondre que pour les nombres réels, car on a une bonne idée de ce que signifie «ne pas gaspiller de bits».

Andrej Bauer

le modèle BSS semble adapté à la géométrie informatique - Voir ma réponse à une question connexe . Le modèle Real RAM utilisé par les géomètres informatiques est antérieur à Blum, Shub et Smale de près d'une décennie.

Jeffε

Réponses:

Je ne sais pas exactement quelle est la question ici, mais je peux essayer d'en dire un peu pour dissiper les éventuels malentendus.

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

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

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

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

Il existe d'anciens théorèmes (voir l'introduction de cet article pour les références) qui expliquent pourquoi ces conditions sont les bonnes. Ces théorèmes montrent également que deux de ces représentations de réels sont calculables isomorphes, c'est-à-dire que nous pouvons les traduire avec des programmes. Cela établit certains critères de correction qui jettent des idées erronées.

Par exemple, j'entends des gens dire des choses comme «les nombres rationnels peuvent être représentés par des informations finies, alors utilisons-les pour des nombres rationnels, et les nombres irrationnels devront être représentés par des informations infinies». Ce genre de chose ne fonctionne pas car il rompt la quatrième condition ci-dessus (considérez une limite de nombres irrationnels - comment direz-vous qu'il converge vers un rationnel?).

Un autre exemple que les conditions ci-dessus éliminent est le modèle Blum-Shub-Smale car il ne permet pas de calculer les limites des séquences. Il vaut mieux dire que le modèle BSS fonctionne sur un sous-champ ordonné discret de réels (généré par tous les paramètres présents), pas sur les réels eux-mêmes.

Parmi les représentations correctes des réels, certaines sont plus efficaces que d'autres, bien que ce soit un sujet quelque peu difficile à discuter car les nombres réels sont des objets infinis. Matthias Schröder a souligné que pour une théorie raisonnable de la complexité, il faut faire attention aux propriétés topologiques de la représentation.

Enfin, comment mesurer la complexité d'une carte , en supposant que nous avons une bonne représentation de ? Parce que est représenté par une fonction, ou un flux infini d'informations, ou quelque chose du genre, nous devrions utiliser l'une des notions de complexité de type supérieur . Lequel dépend probablement de la représentation que vous utilisez. $f : \mathbb{R} \to \mathbb{R}$ $\mathbb{R}$ $x \in \mathbb{R}$

Le modèle BSS est également un modèle de complexité de circuit raisonnable dans lequel nous comptons les opérations arithmétiques. Il est juste bon de garder à l'esprit que ce modèle ne concerne pas les chiffres réels, mais quelque chose d'autre.

Andrej Bauer
la source

Merci beaucoup pour votre réponse et tant de références. Je me sens mal à l'aise à propos de certaines notions de complexité de calcul, permettez-moi de lire la référence et d'y réfléchir pendant un certain temps, et donnez un exemple, si je peux en trouver un qui convient pour expliquer pourquoi je suis si mal à l'aise (cela semble drôle, mais mon expérience me dit si je me sens mal à l'aise, il doit y avoir quelque chose de singulier)

XL _At_Here_There

D'après mon expérience, se sentir mal à l'aise face aux nouvelles connaissances est un bon signe, et généralement c'est une condition préalable à l'illumination.

András Salamon

Un autre modèle éventuellement à explorer est celui du modèle Feasible RAM. Il s'agit d'un modèle de RAM réel modifié pour le calcul réel, de RAM faisable ou d'un modèle de RAM modifié qui utilise à la fois les opérations arithmétiques discrètes et à valeur réelle. Ce modèle permet des opérations réelles et discrètes, et le modèle de Turing est interchangeable avec lui. Le modèle Feasible RAM a une précision définie avec une incertitude, ce qui signifie que permet des comparaisons de nombres réels uniquement jusqu'à une incertitude variable 1 / (k + 1). Cela permet des calculs approximatifs. En outre, comme Vasco Brattkaa et Peter Hertlingb l'affirment dans Feasible Real Random Access Machines - les modèles de Turing et ceux de Feasible Real RAM sont liés. Toutes les fonctions calculables sur une machine de Turing dans le temps $<_{k}$ $O(t)$ sont calculables sur une RAM dans le temps , et dans le cas contraire il y a des frais généraux pour la machine de Turing qui calcule la fonction (si la RAM réelle calcule la fonction dans le TM calcule la fonction dans . Comme souligné les considérations topologiques sont utiles, on ne sait pas si un contexte topologique développé pour ce modèle de calcul permet des calculs réels -qui a une incertitude en précision. $O(t)$ $O(t)$ $O(t^{2}log(t)log(log(t)))$

user3483902
la source

Pourriez-vous donner une référence pour le modèle de RAM possible?

XL _At_Here_There

Voir ci-dessus dans la zone "... cette référence indique ..." a un lien vers l'article.

user3483902

Merci d'avoir souligné le travail de Brattka & Hertling, j'allais le mentionner d'ici là, j'oubliais. Je voudrais simplement souligner que le modèle de RAM faisable ne comprend aucune fonction d'ordre supérieur, en particulier il ne peut pas calculer la limite d'une séquence de Cauchy (rapide), donc je ne le considérerais pas comme implémentant précisément "les réels". Il peut calculer une limite "au niveau supérieur", pour ainsi dire (voir la partie de l'article où ils parlent d'approximations rationnelles des fonctions).

Andrej Bauer