Des problèmes de somme de racines carrées?

Le problème de la somme des racines carrées pose, étant donné deux séquences $a_1, a_2, \dots, a_n$ et $b_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; voir ce post$\sum_i \sqrt{a_i}$$\sum_i \sqrt{b_i}$pour plus de détails. Ce problème se pose naturellement dans la géométrie informatique, en particulier dans les problèmes impliquant les chemins les plus courts euclidiens, et constitue un obstacle important au transfert d'algorithmes pour ces problèmes de la RAM réelle à la RAM entière standard.

Appelez un problème Π somme-de-racines-carrées-dures-dur (abrégé √-dur?) S'il y a une réduction polynomiale du problème de la somme des racines carrées à Π. Il n’est pas difficile de prouver que le problème suivant est la somme des racines carrées:

Les plus courts chemins dans les graphes géométriques euclidiens 4d

Instance: Un graphe $G=(V,E)$ dont les sommets sont des points de , avec des arêtes pondérées par la distane euclidienne; deux sommets et$\mathbb{Z}^4$$s$$t$

Sortie: le plus court chemin de à dans .$s$$t$$G$

Bien sûr, ce problème peut être résolu en temps polynomial sur la RAM réelle en utilisant l'algorithme de Dijkstra, mais chaque comparaison dans cet algorithme nécessite la résolution d'un problème de somme de racines carrées. La réduction utilise le fait que tout nombre entier peut être écrit comme la somme de quatre carrés parfaits; la sortie de la réduction est en réalité un cycle sur sommets.$2n+2$

Quels sont les autres problèmes de la somme des racines carrées? Je suis particulièrement intéressé par les problèmes pour lesquels il existe une solution polynomiale sur la RAM réelle. Voir ma question précédente pour une possibilité.

Comme Robin le suggère, les réponses ennuyeuses sont ennuyeuses. Pour toute classe de complexité X contenant une somme de racines carrées (par exemple, PSPACE ou EXPTIME), chaque problème X-hard est ennuyeusement une somme de racines carrées.

Cela a été un peu discuté dans le sondage suivant (diapositive de départ 21): http://homepages.inf.ed.ac.uk/kousha/games08_tutorial.pdf

qui mentionne le TSP euclidien, l'approximation de l'équilibre de Nash actuel et les classes PosSLP et FIXP.

Cela devrait être un commentaire, car c’est une réponse plutôt ennuyeuse, mais je n’ai pas assez de réputation.

La somme des problèmes de la racine carrée est en de [ABKM98] , de sorte que tout problème difficile pour cette classe a la propriété requise. Cela se fait en réduisant le problème de la somme des racines carrées à un problème appelé P o s S L P , défini comme décider si un problème en ligne droite représente un entier positif, de sorte que le problème est la somme des racines carrées. dur.$P^{PP^{PP^{PP}}}$$PosSLP$

[ABKM98]: De la complexité de l'analyse numérique, par Allender, Burgisser, Kjeldgaard-Pedersen et Miltersen.