A continuous optimization problem that reduces to TSP

Question

Suppose I am given a finite set of points $p_1,p_2,..p_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p_i$'s, such that its perimeter is as small as possible. Assuming $p_i=(x_i,y_i)$ and $x_i<x_{i+1}$, I can formalize this problem as:

Problem 1 (edited in response to Suresh's comments) Determine $C^2$ functions $x(t),y(t)$ of a parameter $t$ such that the arclength $ L = \int_{[t \in 0,1]} \sqrt{x'^2+y'^2}dt$ is minimized, with $x(0) = x_1, x(1) = x_n$ and for all $t_i: x(t_i) = x_i$, we have $y(t_i)=y_i)$.

How do I prove (or perhaps refute) that Problem 1 is NP-hard?

Why I suspect NP-hardness Suppose the $C^2$ assumption is relaxed. Evidently, the function of minimal arclength is the Travelling Salesman tour of the $p_i$'s. Perhaps the $C^2$ constraint only makes the problem much harder?

Context A variant of this problem was posted on MSE. It didn't receive an answer both there and on MO. Given that it's nontrivial to solve the problem, I want to establish how hard it is.

Answer 1

The differentiability requirement doesn't change the nature of the problem: requiring $\mathcal{C}^0$ (continuity) or $\mathcal{C}^{\infty}$ (infinite differentiability) gives the same lower bound for the length and the same order of points, and is equivalent to solving the traveling salesman problem.

If you have a solution to the TSP, you have a $\mathcal{C}^0$ curve that goes through all the points. Conversely, suppose you have a $\mathcal{C}^0$ curve of finite length that goes through all the points, and let $p_{\sigma(1)}, \ldots, p_{\sigma(n)}$ be the order in which it traverses the points and $t_1,\ldots,t_n$ the corresponding parameters (if the curve traverses a point more than once, pick any of the possible values of $t$). Then the curve built from $n$ segments $[p_{\sigma(1)},p_{\sigma(2)}], \ldots, [p_{\sigma(n-1)},p_{\sigma(n)}], [p_{\sigma(n)},p_{\sigma(1)}]$ is shorter, because for each segment a straight line is shorter than any other curve that connects the point. Thus for every ordering of the points, the best curve is a TSP solution, and the TSP solution provides the best ordering of the points.

Let's now show that requiring the curve to be $\mathcal{C}^{\infty}$ (or $\mathcal{C}^k$ for any $k$) doesn't change the best ordering of points. For any TSP solution of total length $\ell$ and any $\epsilon > 0$, we can round every corner, i.e. build a $\mathcal{C}^{\infty}$ curve that traverses the points in the same order and has a length of at most $\ell + \epsilon$ (the explicit construction relies on algebraic functions and $e^{-1/t^2}$ to define bump functions and from those smooth connections between curve segments such as $e^{1-1/x^2} (x-e^{-1/(1-x)^2})$ which connects with $y=0$ at $x=0$ and with $y=x$ at $x=1$; it is tedious to make these explicit, but they are computable); hence, the lower bound for a $\mathcal{C}^{\infty}$ curve is the same as for a collection of segments (note that the lower bound is not reached in general).