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

Supongamos que yo soy dado un conjunto finito de puntos en el plano, y se le pidió que dibujara una curva C ( P ) dos veces diferenciable a través de los p i 's, de modo que su perímetro sea lo más pequeño posible. Suponiendo que p i = ( x i , y i ) y x i < x i + 1 , puedo formalizar este problema como:$p_1,p_2,..p_n$$C(P)$$p_i$$p_i=(x_i,y_i)$$x_i<x_{i+1}$

Problema 1 (editado en respuesta a los comentarios de Suresh) Determine las funciones de x ( t ) , y ( t ) de un parámetro t tal que la longitud del arco L = ∫ [ t ∈ 0 , 1 ] $C^2$$x(t),y(t)$$t$ se minimiza, conx(0)=x1,x(1)=xny para todoti:x(ti)=xi, tenemosy(ti)=yi).$L = \int_{[t \in 0,1]} \sqrt{x'^2+y'^2}dt$$x(0) = x_1, x(1) = x_n$$t_i: x(t_i) = x_i$$y(t_i)=y_i)$

¿Cómo pruebo (o tal vez rechazo) que el problema 1 es NP-difícil?

Por qué sospecho de dureza NP Suponga que la suposición de es relajada. Evidentemente, la función de la longitud de arco mínima es el recorrido del vendedor ambulante de los p i 's. ¿Quizás la restricción C 2 solo hace que el problema sea mucho más difícil?$C^2$$p_i$$C^2$

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

$\mathcal{C}^0$$\mathcal{C}^{\infty}$

$\mathcal{C}^0$$\mathcal{C}^0$$p_{\sigma(1)}, \ldots, p_{\sigma(n)}$$t_1,\ldots,t_n$$t$$n$$[p_{\sigma(1)},p_{\sigma(2)}], \ldots, [p_{\sigma(n-1)},p_{\sigma(n)}], [p_{\sigma(n)},p_{\sigma(1)}]$es más corta, 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 ordenamiento de los puntos, la mejor curva es una solución TSP, y la solución TSP proporciona el mejor ordenamiento de los puntos.

$\mathcal{C}^{\infty}$$\mathcal{C}^k$$k$$\ell$$\epsilon > 0$$\mathcal{C}^{\infty}$$\ell + \epsilon$$e^{-1/t^2}$$e^{1-1/x^2} (x-e^{-1/(1-x)^2})$$y=0$$x=0$$y=x$$x=1$$\mathcal{C}^{\infty}$