Contexte Le calcul sur des nombres réels est plus compliqué que celui sur des nombres naturels, puisque les nombres réels sont des objets infinis et qu'il existe un nombre incalculable de nombres réels. Par conséquent, les nombres réels ne peuvent être fidèlement représentés par des chaînes finies...
Le problème de la somme des racines carrées pose, étant donné deux séquences a1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n et b1,b2,…,bnb1,b2,…,bnb_1, b_2, \dots, b_n d’entiers positifs, si la somme inférieure à, égale à to, ou supérieure à la somme . Le statut de complexité de ce problème est ouvert;...
L'un des Saint Graal de la conception d'algorithmes est de trouver un algorithme fortement polynomial pour la programmation linéaire, c'est-à-dire un algorithme dont l'exécution est délimitée par un polynôme dans le nombre de variables et de contraintes et est indépendante de la taille de la...
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...
Supposons que l'on nous donne plusieurs polygones simples disjoints dans le plan, et deux points et t à l' extérieur de chaque polygone. Le problème du chemin le plus court euclidien consiste à calculer le chemin le plus court euclidien de s à t qui ne coupe pas l'intérieur d'un polygone. Pour être...
Actuellement, le calcul des réels dans les langages les plus populaires se fait toujours via des opérations en virgule flottante. D'un autre côté, des théories comme l'effectivité de type deux (TTE) et la théorie des domaines promettent depuis longtemps le calcul exact des réels. De toute évidence,...
Quelle est la complexité (sur la RAM entière standard) du calcul de la transformée de Fourier discrète standard d'un vecteur de nombres entiers?nnn L' algorithme classique pour les transformées de Fourier rapides , attribué de manière inappropriée [1] à Cooley et Tukey, est généralement décrit...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Une question récente a discuté de l'algorithme de programmation dynamique désormais classique pour TSP, dû indépendamment à Bellman et Held-Karp . Il est universellement rapporté que l' algorithme s'exécute en temps . Cependant, comme l'un de mes étudiants l'a récemment souligné, ce temps...
Existe-t-il un théorème général qui indiquerait, avec une désinfection appropriée, que la plupart des résultats connus concernant l'utilisation de nombres réels peuvent réellement être utilisés lorsque l'on considère uniquement les réels calculables? Ou existe-t-il une caractérisation appropriée...
J'étudie récemment le modèle de calcul BSS (cf. par exemple Complexité et calcul réel; Blum, Cucker, Shub, Smale.) Pour les réels , on montre que, étant donné un système de polynômes f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] , l'existence de zéros est N P R -complète. Cependant, je me demande si ces f...
Dans cette note de cours d'Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf , il est dit que nous ne savons pas si le TSP euclidien est en NP: La raison étant que nous ne savons pas calculer efficacement les racines carrées. D'autre part, il y a cet article de...
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...
Quelqu'un peut-il m'indiquer la référence pour la non-définissabilité du module de continuité fonctionnelle en PCF? \ newcommand {\ bool} {\ mathsf {bool}}\newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Andrej Bauer a écrit un très bon article de blog explorant certains des problèmes...
En utilisant le modèle réel RAM / BSS, nous avons la classe NP , (où un BSS est le modèle Blum-Shub-Smale d'un ordinateur avec des opérations sur des réels). Nous avons des problèmes complets de NP _ {\ mathbb {R}} . Donc, la question est de savoir s'il existe un analogue de la conjecture de Berman...