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

37

Le problème de la somme des racines carrées pose, étant donné deux séquences a1,a2,,an et b1,b2,,bn 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 postiaiibipour 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 etZ4st

Sortie: le plus court chemin de à dans .stG

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.

Jeffε
la source
1
Merci à Suresh et Peter d’avoir suggéré cette question.
Jeff E
8
Peut-être pourriez-vous également exclure les réponses triviales en insistant sur le fait que les réponses ne doivent pas être uniquement des problèmes difficiles pour une classe connue pour contenir le problème Somme des racines carrées. Par exemple, tout problème difficile avec PSPACE serait une somme de racines carrées, mais ce n'est probablement pas intéressant.
Robin Kothari
Voulez-vous vraiment dire dans votre énoncé de problème du plus court chemin, ou Z 4 ? Le premier ne semble pas pouvoir utiliser une RAM entière, et probablement le problème est toujours difficile à restreindre à des points entiers ...R4Z4
Steven Stadnicki -
@ Steven: Oui, vous avez raison. Édité.
Jeffε

Réponses:

21

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.PPPPPPPPosSLP

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

Abel Molina
la source
9
Il y a aussi cette amélioration [ mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf] qui met le problème en et prouve aussi qu'une version limitée du problème a besoin d' un nombre polynomial de bits. CoRPPP
Elias
1
@Elias: Pouvez-vous élaborer? De prime abord, Kayal et Saha semblent discuter de la «version polynomiale» du problème de la somme des racines carrées, qui est liée au problème de la somme des racines carrées, mais en est différente.
Tsuyoshi Ito
1
@Abel: (1) Bonjour Abel, content de voir ton message! (2) Pour ce que ça vaut, [ABKM98] a été présenté à la conférence CCC 2006 et publié en 2009 . (3) Une réponse ennuyeuse ne devrait pas être un commentaire, mais devrait être gardée pour vous. Mais je ne pense pas que cette réponse soit ennuyeuse. :)
Tsuyoshi Ito
1
@Tsuyoshi: Ils ont complètement résolu la version polynomiale du problème. Sur la base de cela , ils prouvent que si sont d' une forme particulière, à savoir un i = Σ i b i j X j i - jX > ( B + 1 ) ( n d ) O ( 1 ) , B = m a x { b i j } et d = m a x {aiai=ibijXdijX>(B+1)(nd)O(1)B=max{bij} , il faut alors un nombre polynomial de bits pour trancher le problème. d=max{di}
Elias
3
@Tsuyoshi: J'ai complètement mal compris votre question. Je suis désolé pour cela. Qu'est - ce que Kayal et Saha prouvent que DegSLP est en . Je devrais être plus prudent. Merci pour ça. CoRPPP
Elias