Un problema de optimización continua que se reduce a TSP

Question

Supongamos que me dan un conjunto finito de puntos $ p_1, p_2, .. p_n $ en el avión, y se me pidió que dibuje una curva de dos veces diferenciable $ c (p) $ a través del $ p_i $ s, de modo que su perímetro es lo más pequeño posible. Suponiendo $ p_i = (x_i, y_i) $ y $ x_i

Problema 1 (editado en respuesta a los comentarios de Suresh) Determine $ c^2 $ funciones $ x (t), y (t) $ de un parámetro $ t $ de modo que el arcle longitud $ l = int _ {[t in 0,1]} sqrt {x '^2 +y '^2} dt $ se minimiza, con $ x (0) = x_1, x (1) = x_n $ y para todo $ t_i: x (t_i) = x_i $, tenemos $ y (t_i) = y_i ps

¿Cómo pruebo (o tal vez refutar) que el problema 1 es NP-Hard?

Por qué sospecho que NP-Hardness Supongamos que la suposición de $ C^2 $ es relajada. Evidentemente, la función de Minimal Arclength es el recorrido de vendedor ambulante de los $ P_i $ 's. ¿Quizás la restricción de $ C^2 $ solo hace que el problema sea mucho más difícil?

Contexto Se publicó una variante de este problema en MSE. No recibió una respuesta tanto allí como en mes. Dado que no es trivial resolver el problema, quiero establecer lo difícil que es.

Answer 1

El requisito de diferenciabilidad no cambia la naturaleza del problema: requerir $ mathcal {c}^0 $ (continuidad) o $ mathcal {c}^{ infty} $ (infinita diferenciabilidad) da el mismo límite inferior para el límite inferior para el límite inferior para el límite inferior para el límite inferior para Longitud y el mismo orden de puntos, y es equivalente a resolver el problema del vendedor ambulante.

Si tiene una solución al TSP, tiene una curva $ mathcal {c}^0 $ que pasa por todos los puntos. Por el contrario, suponga que tiene una curva de longitud finita $ mathcal {c}^0 $ que pasa por todos los puntos, y deje $ P _ { sigma (1)}, ldots, p _ { sigma (n)} $ Sea el orden en el que atraviesa los puntos y $ t_1, ldots, t_n $ los parámetros correspondientes (si la curva atraviesa un punto más de una vez, elija cualquiera de los valores posibles de $ t $). Luego, la curva construida a partir de $ n $ segmentos $ [p _ { sigma (1)}, p _ { sigma (2)}], ldots, [p _ { sigma (n-1)}, p _ { sigma (Sigma ( n)}], [p _ { sigma (n)}, p _ { sigma (1)}] $ es más corto, porque para cada segmento una línea recta es más corta que cualquier otra curva que conecta el punto. Por lo tanto, para cada pedido de los puntos, la mejor curva es una solución TSP, y la solución TSP proporciona el mejor pedido de los puntos.

Ahora demostremos que exigir que la curva sea $ mathcal {c}^{ infty} $ (o $ mathcal {c}^k $ por cualquier $ k $) no cambia el mejor pedido de puntos. Para cualquier solución TSP de longitud total $ ell $ y cualquier $ epsilon> 0 $, podemos redondear cada esquina, es decir, construir una curva $ mathcal {c}^{ infty} $ que atraviesa los puntos en el mismo orden y tiene una longitud de como máximo $ ell + epsilon $ (la construcción explícita se basa en funciones algebraicas y $ e^{-1/t^2} $ para definir Funciones de golpe y de esas conexiones suaves entre segmentos de curva como $ e^{1-1/x^2} (xe^{-1/(1-x)^2}) $ que se conecta con $ y = 0 $ a $ x = 0 $ y con $ y = x $ a $ x = 1 $; Es tedioso hacer estos explícitos, pero son computables); Por lo tanto, el límite inferior para una curva $ mathcal {c}^{ infty} $ es la misma que para una colección de segmentos (tenga en cuenta que el límite inferior no se alcanza en general).