Un problème d'optimisation continue qui réduit à TSP

Question

Supposons que je suis donné un ensemble fini de points $ p_1, p_2, .. p_n $ dans le plan, et demandé de dessiner une courbe bi-différentiable $ C (P) $ dans le p_i de $ $ 's, de telle sorte que son périmètre est aussi faible que possible. En supposant $ p_i = (x_i, y_i) $ et x_i $

Problème 1 (édité en réponse aux commentaires de Suresh) Calculer $ C ^ 2 fonctions $ $ x (t), y (t) $ d'un paramètre $ t $ de telle sorte que la longueur d'arc $ L = \ int _ {[t \ à 0,1]} \ sqrt {x ^ 2 + y ^ 2} dt $ est réduite au minimum, avec $ x (0) = x 1, x (1) = x_n $ pour toutes $ t_i: x (t_i) = x_i $, nous avons $ y (t_i) = y_i) $.

  

Comment puis-je prouver (ou réfutent peut-être) ce problème 1 est NP-dur?

Pourquoi je soupçonne NP-dureté Supposons que l'hypothèse de $ C $ ^ 2 est détendu. De toute évidence, la fonction de arclength minimale est la tournée Salesman Travelling des P_i $ $ s '. Peut-être la contrainte $ $ C ^ 2 ne fait que le problème est beaucoup plus difficile?

Contexte Une variante de ce problème a été publié sur MSE . Il n'a pas reçu une réponse à la fois là et sur MO . Étant donné qu'il est non négligeable pour résoudre le problème, je veux établir combien il est difficile.

Answer 1

L'exigence de différentiabilité ne change pas la nature du problème: nécessitant $ \ mathcal {C} ^ 0 $ (continuité) ou $ \ mathcal {C} ^ {\ infty} $ (différentiabilité infini) donne la même inférieure lié à la longueur et le même ordre de points, et est équivalent à résoudre le problème du voyageur de commerce.

Si vous avez une solution au TSP, vous avez un mathcal $ \ {C} ^ 0 courbe de $ qui passe par tous les points. A l'inverse, supposons que vous avez un $ \ mathcal {C} ^ 0 courbe $ de longueur finie qui passe par tous les points, et que $ p _ {\ sigma (1)}, \ ldots, p _ {\ sigma (n)} $ soit l'ordre dans lequel il traverse les points et t_1 $, \ ldots, t_n $ les paramètres correspondants (si la courbe traverse un point plus d'une fois, choisir l'une des valeurs possibles de $ t $). Ensuite, la courbe construite à partir de $ n segments $ $ [p _ {\ sigma (1)}, p _ {\ sigma (2)}], \ ldots, [p _ {\ sigma (n-1)}, p _ {\ sigma ( n)}], [p _ {\ sigma (n)}, p _ {\ sigma (1)}] $ est plus courte, parce que, pour chaque segment d'une ligne droite est plus courte que toute autre courbe qui relie le point. Ainsi, pour chaque commande des points, la meilleure courbe est une solution de TSP, et la solution de TSP offre le meilleur classement des points.

Montrons maintenant que nécessitant la courbe à $ \ mathcal {C} ^ {\ infty} $ (ou $ \ mathcal {C} ^ k $ pour tout k $ $) ne change pas le meilleur classement de points . Pour toute solution de TSP de longueur totale $ \ ell $ et tout $ \ epsilon> 0 $, nous pouvons arrondir tous les coins, à savoir construire un $ \ mathcal {C} ^ {\ infty} $ courbe qui traverse les points dans le même ordre et a une longueur d'au plus $ \ ell + \ epsilon $ (la construction explicite repose sur les fonctions algébriques et $ e ^ {- 1 / t ^ 2} $ pour définir bump fonctions et de ces connexions entre les segments de courbe tels que $ e ^ {1-1 / x ^ 2} ({xe ^ - 1 / (1-x) ^ 2} ) $ qui se connecte avec $ y = 0 $ à $ x = 0 $ et $ y = x $ à $ x = 1 $, il est fastidieux de les rendre explicites, mais ils sont calculables); Par conséquent, la limite inférieure pour un $ \ mathcal {C} ^ {\ infty} $ courbe est la même que pour un ensemble de segments (notez que la limite inférieure n'est pas atteint en général).