TSP euclidien en complexité NP et racine carrée

12

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 Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 disant qu'il est NP-complet, ce qui signifie également qu'il est en NP. Bien qu'il ne le prouve pas dans le journal, je pense qu'il considère l'appartenance à NP insignifiante, comme c'est généralement le cas avec de tels problèmes.

Je suis confus par cela. Honnêtement, l'affirmation selon laquelle nous ne savons pas si le TSP euclidien est en NP m'a choqué, car je pensais simplement que c'était trivial - en prenant le tour du TSP comme certificat, nous pouvons facilement vérifier qu'il s'agit d'un tour valide. Mais le problème est qu'il peut y avoir des racines carrées. Les notes de cours prétendent donc que nous ne pouvons pas résoudre en temps polynomial le problème suivant:

Étant donné le nombre rationnel , décider si q1,,qn,AQ.q1++qnA

Question 1: Que savons-nous de ce problème?

Cela demande la simplification suivante, que je n'ai pas pu trouver:

Question 2: Est-ce réductible au cas particulier lorsque ? Ce cas spécial est-il résoluble en temps polynomial?n=1

En y réfléchissant un moment, j'y suis arrivé. Nous voulons une complexité temporelle polynomiale par rapport au nombre de bits de l'entrée, c'est-à-dire pas à la taille des nombres eux-mêmes. Nous pouvons facilement calculer la somme d'un nombre polynomial de chiffres décimaux. Pour obtenir un mauvais cas, nous avons besoin d'une instance de pour k = 1 , 2 , telle que pour chaque polynôme p , il existe un entier k tel que q1,k,,qn,k,AkQk=1,2,pk etAks'accordent sur lesppremierschiffres(taille d'entrée)de l'expansion décimale.q1,k++qn,kAkp(input-size)

Question 3: existe-t-il une telle instance de nombre de création?

Mais qu'est ? Cela dépend de la façon dont les nombres rationnels sont représentés! Maintenant, je suis curieux à ce sujet:input-size

Question 4: Is est algorithmiquement important si nombre rationnel sont données à titre rapport de deux nombres entiers (tels que ) ou dans le développement décimal (tels que 2,5334 ¯ 567 )? En d'autres termes, existe-t-il une famille de nombres rationnels tels que la taille de l'expansion décimale n'est pas polynomiale dans la taille de la représentation des rapports ou l'inverse?24/132.5334567¯

JS_
la source
2bq110000b length 

Réponses:

19

nn

n=1qA2

a1,,ak,b1,,bk1n|i=1kaii=1kbi|=O(n2k+3/2)Ω(2klogn)k

Q4. Je pense que la représentation décimale pourrait être assez inefficace. La longueur de la période est l'ordre multiplicatif de 10 modulo le dénominateur, qui peut être exponentiel en nombre de bits du dénominateur.

Sasho Nikolov
la source
NP
@Lamine Bien sûr, qu'est-ce que l'un a à voir avec l'autre?
Sasho Nikolov
3

Tu as écrit:

D'autre part, il y a cet article de Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 disant qu'il est NP-complet, ce qui signifie également qu'il est en NP. Bien qu'il ne le prouve pas dans le journal, je pense qu'il considère l'appartenance à NP insignifiante, comme c'est généralement le cas avec de tels problèmes.

Pourquoi ne lisez-vous pas simplement le journal au lieu de publier de telles affirmations absurdes? À la page 239, Papadimitriou discute soigneusement de ces problèmes et définit la variante sous-jacente de la métrique euclidienne pour sa preuve.

Gamow
la source
6
Je pense que cela vaut mieux un commentaire qu'une réponse, à moins que vous ne fournissiez des détails sur la façon dont Papadimitriou évite le problème de la somme des racines carrées.
Sasho Nikolov