Comment les nombres réels sont-ils spécifiés dans le calcul?

27

C'est peut-être une question fondamentale, mais j'ai lu et essayé de comprendre des articles sur des sujets tels que le calcul de l'équilibre de Nash et les tests de dégénérescence linéaire et je ne savais pas comment les nombres réels sont spécifiés en entrée. Par exemple, quand il est indiqué que LDT a certaines bornes inférieures polynomiales, comment les nombres réels sont-ils spécifiés lorsqu'ils sont traités en entrée?

cc.complexity-theory computability na.numerical-analysis computing-over-reals computable-analysis Philip White
la source
1
Vous pouvez trouver la discussion ici intéressante: en.wikipedia.org/wiki/Computable_number
Joseph Malkevitch
Quelqu'un devrait rassembler ces documents dans un livre électronique téléchargeable gratuitement.
Dilawar

Réponses:

34

Je ne suis pas d'accord avec votre réponse acceptée par Kaveh. Pour la programmation linéaire et les équilibres de Nash, la virgule flottante peut être acceptable. Mais les nombres à virgule flottante et la géométrie de calcul se mélangent très mal: l'erreur d'arrondi invalide les hypothèses combinatoires des algorithmes, les faisant fréquemment planter. Plus précisément, de nombreux algorithmes de géométrie de calcul dépendent de tests primitifs qui vérifient si une valeur donnée est positive, négative ou nulle. Si cette valeur est très proche de zéro et que l'arrondi en virgule flottante lui donne le mauvais signe, de mauvaises choses peuvent se produire.

Au lieu de cela, les entrées sont souvent supposées avoir des coordonnées entières, et les résultats intermédiaires sont souvent représentés exactement, soit sous forme de nombres rationnels avec une précision suffisamment élevée pour éviter le débordement, soit sous forme de nombres algébriques. Des approximations en virgule flottante de ces nombres peuvent être utilisées pour accélérer les calculs, mais uniquement dans des situations où les nombres peuvent être garantis suffisamment éloignés de zéro pour que les tests de signe donnent les bonnes réponses.

Dans la plupart des articles sur les algorithmes théoriques en géométrie computationnelle, ce problème est contourné en supposant que les entrées sont des nombres réels exacts et que les primitives sont des tests exacts des signes de racines de polynômes de faible degré dans les valeurs d'entrée. Mais si vous implémentez des algorithmes géométriques, tout cela devient très important.

David Eppstein
la source
J'avais aimé la partie de la réponse de Kaveh où il a suggéré qu'il existe d'autres modèles de calcul, car cela semblait être conforme à ce que j'avais lu dans le document que je regardais. Cela dit, je ne connaissais pas vraiment la réponse ... Je n'ai pas accepté la réponse de Kaveh pour l'instant. J'avais en fait soupçonné que les nombres algébriques pouvaient avoir quelque chose à voir avec ça. Quoi qu'il en soit, merci d'avoir pris le temps de réfléchir à ma question ... Je réfléchirai et lirai avant d'accepter une réponse.
Philip White
Je n'ai pas dit que c'est un bon modèle pour CG, mon point était que même lorsque les auteurs disent que les entrées sont des nombres réels, ce ne sont pas vraiment des nombres réels . Je suis d'accord avec vous que je n'aurais pas dû inclure CG parmi les autres. J'ai lu un très petit nombre d'articles CG, le modèle BSS est-il bien établi dans les articles CG théoriques?
Kaveh
1
Pardonnez mon ignorance, mais que signifie BSS?
Philip White
1
Le modèle BSS est un modèle théorique qui suppose que des nombres réels arbitraires sont disponibles. Ce qui se fait en CG implique des implémentations réelles d'un modèle qui est généralement limité aux nombres algébriques. De plus, les implémentations CG sont loin du coût unitaire par opération. Ce n'est donc pas la même chose. Voir par exemple le modèle de nombre réel LEDA, citeseerx.ist.psu.edu/viewdoc/…
David Eppstein
10
@Kaveh: Non. Les algorithmes géométriques sont conçus pour être corrects, dans le modèle RAM réel, pour une entrée réelle arbitraire, pas seulement pour une entrée rationnelle. En particulier, il existe des algorithmes géométriques qui ne peuvent pas être implémentés exactement, car ils utilisent des primitives triviales sur la RAM réelle mais pour lesquelles aucun algorithme efficace n'est connu pour la RAM entière (réaliste). Le meilleur exemple est le problème de la somme des racines carrées: étant donné deux ensembles et d'entiers positifs, est ? T ∑ s ∈ S √ST∑s∈Ss>∑t∈Tt
Jeffε
8

Ce n'est pas une réponse directe à votre question, plutôt une réponse à Raphaël . Il y a eu pas mal de travaux récemment spécifiant des calculs de nombres réels utilisant la coinduction. Voici quelques articles sur le sujet.

Ils couvrent à peine le spectre complet du calcul des nombres réels, mais des progrès sont en cours pour éliminer divers problèmes.

Dave Clarke
la source
1
Bonne idée, mais comme vous ne pouvez compter que de nombreuses définitions coinductives, cette approche ne peut pas couvrir l'ensemble . Dois-je oublier quelque chose? Ou ai-je mal compris et le but est de représenter au moins quelques chiffres exactement? R
Raphael
Bon point. Je ne sais pas quelles sont les limites de l'approche coinductive. L'approche en est à ses balbutiements.
Dave Clarke
7

La complexité de calcul des calculs sur des nombres réels est considérée par Blum, Cucker, Shub et Smale . Voici une description partielle du livre:

La théorie classique du calcul trouve ses origines dans les travaux de Goedel, Turing, Church et Kleene et a été un cadre extraordinairement efficace pour l'informatique théorique. La thèse de ce livre, cependant, est qu'il fournit une base inadéquate pour le calcul scientifique moderne où la plupart des algorithmes sont des algorithmes en nombre réel. Le but de ce livre est de développer une théorie formelle du calcul qui intègre les thèmes majeurs de la théorie classique et qui soit plus directement applicable aux problèmes de mathématiques, d'analyse numérique et de calcul scientifique. En cours de route, les auteurs examinent des problèmes fondamentaux tels que: l'ensemble de Mandelbrot est-il décidable? Pour les cartes quadratiques simples, l'ensemble Julia est-il un ensemble d'arrêt? Quelle est la vraie complexité de Newton? méthode s? Existe-t-il un algorithme pour décider du problème du sac à dos en plusieurs étapes? La Hilbert Nullstellensatz est-elle intraitable? Le problème de la localisation d'un zéro réel d'un degré quatre est-il insoluble? La programmation linéaire est-elle traitable sur les réels?

Vous pouvez trouver une critique de ce livre sur ACM SIGACT News .

MS Dousti
la source
Ce livre a l'air très intéressant, merci.
Philip White
Je vous en prie.
MS Dousti
5
Il convient de noter que le modèle de calcul BSS sur les réels est controversé, pour des raisons similaires à celles évoquées par David Eppstein dans un commentaire ci-dessus. Par exemple: l'axiome BSS qui calcule si x <y prend un pas de temps, pour des réels arbitraires x et y. En revanche, des approches telles que l'efficacité de type deux (TTE) définissent des machines qui prennent comme approximations d'entrée des réels et des approximations calculables en sortie des fonctions par rapport aux réels. Plus le temps s'écoule, meilleures sont les approximations d'entrée et de sortie. Cette approche me semble plus réaliste.
Aaron Sterling
@Aaron Sterling: connaissez-vous une bonne référence pour l'efficacité de type deux?
Joshua Grochow
3
@Joshua Grochow: Désolé, je n'y suis pas arrivé plus tôt. Le livre lié à Kaveh est le "Nielsen et Chuang" de TTE. Cependant, il est tellement chargé de notation qu'il semblerait mystérieux à un lecteur occasionnel. Je suggérerais plutôt les diapositives suivantes du didacticiel de Vasco Brattka: cca-net.de/vasco/cca/tutorial.pdf
Aaron Sterling
7

Modifié / corrigé en fonction des commentaires

Lorsque les auteurs parlent d'entrées de nombres réels dans la programmation linéaire, de calcul d'équilibre de Nash, ... dans la plupart des articles (articles qui ne traitent pas du calcul / de la complexité par rapport aux nombres réels), ils ne signifient pas vraiment des nombres réels. Ce sont des nombres rationnels et des nombres qui en découlent en raison de leurs manipulations (nombres algébriques). Vous pouvez donc les considérer comme représentés par des chaînes finies.

D'un autre côté, si l'article porte sur la calculabilité et la complexité de l'analyse , ils n'utilisent pas le modèle habituel de calcul, et il existe différents modèles incompatibles de calcul / complexité sur des nombres réels.

Si l'article ne spécifie pas de modèle de calcul sur des nombres réels, vous pouvez supposer en toute sécurité qu'il s'agit du premier cas, c'est-à-dire qu'il ne s'agit que de nombres rationnels.

La géométrie informatique est différente. Dans la plupart des articles de CG, si les auteurs ne précisent pas quel est le modèle qui, en ce qui le concerne, l'exactitude et la complexité d'un algorithme sont discutées, il peut être supposé être le modèle BSS (aka real-RAM).

Le modèle n'est pas réaliste et la mise en œuvre n'est donc pas simple. (C'est l'une des raisons pour lesquelles certaines personnes au CCA préfèrent les modèles théoriques Ko-Friedman / TTE / Domain , mais le problème avec ces modèles est qu'ils ne sont pas aussi rapides que le calcul à virgule flottante dans la pratique.) La justesse et la complexité de l'algorithme dans le modèle BSS ne se transfère pas nécessairement à l'exactitude de l'algorithme implémenté.

Le livre de Weihrauch contient une comparaison entre différents modèles (section 9.8). Il ne fait que trois pages et mérite d'être lu.

(Il existe également une troisième méthode, qui peut être plus adaptée à la CG, vous pouvez consulter ce document:

Chee Yap, " Théorie du calcul réel selon EGC "

où EGC est le calcul géométrique exact .)

Kaveh
la source
Je pense que l'article qui m'intéresse principalement spécifie un modèle, étant donné qu'il comprend la phrase «Nous définissons maintenant formellement notre modèle de calcul». Le document s'intitule «Limites inférieures pour les problèmes de satisfaction» et il semble y avoir une discussion sur les arbres de décision linéaires et les polynômes de requête. Donc, je pense que c'est la réponse que je cherchais là-bas ... merci. Je vais relire le document et voir si je peux le comprendre.
Philip White
2
Je ne suis pas d'accord. Ce n'est pas le bon modèle pour la géométrie de calcul. Voir ma réponse plus détaillée ci-dessous.
David Eppstein
1
@Kaveh: Je pense que vous devriez dire que ce sont des nombres rationnels , pas des nombres à virgule flottante. Les nombres rationnels exacts sont faciles à représenter par des chaînes finies, et dans de nombreuses applications (par exemple, celles liées à la programmation linéaire) les résultats intermédiaires seront également des nombres rationnels si vos entrées sont des nombres rationnels. (Bien sûr, comme l'a souligné David Eppstein, la géom. Comp. Est une exception notable dans le sens où les résultats intermédiaires ne sont généralement pas rationnels.)
Jukka Suomela
@Jukka: Vous avez raison, je remplacerai la virgule flottante par rationnelle.
Kaveh
5
Nan. Quand j'écris "vrai nombre", je veux dire vraiment "vrai nombre", et par là je veux dire vraiment vrai nombre, vraiment à partir des réels. Vraiment. En particulier, dans l'article dont parle @Philip, je dois supposer que les algorithmes fonctionnent pour des entrées réelles arbitraires , afin de pouvoir appliquer les résultats d'une analyse non standard.
Jeffε
3

Ils ne le sont pas et ne le peuvent pas, en général. Nous ne pouvons traiter qu'un nombre dénombrable d'entrées (et de sorties et de fonctions) avec nos modèles de calcul. En particulier, toute entrée doit être finie mais tous les nombres réels n'ont pas de représentations finies.

Vous pourriez, je suppose, supposer une sorte d'oracle qui donne le prochain chiffre d'un certain nombre réel sur demande (qch comme un flux). Sinon, vous devrez vivre avec des approximations (arbitrairement précises).

Raphael
la source
Si cela est vrai, comment LDT peut-il gérer les nombres réels? J'ai lu quelque chose à propos des «arbres de décision r-linéaires», mais je n'ai pas vraiment compris de quoi ils parlaient dans l'article, «Limites inférieures pour les problèmes de satiabilité linéaire».
Philip White
Je parie qu'ils ne le peuvent pas ou qu'ils n'utilisent pas de machines Turing (ou des concepts équivalents). Les autres réponses qui ne sont pas aussi strictes / générales que les miennes devraient éclairer cela.
Raphael