Masalah optimisasi berkelanjutan yang mereduksi menjadi TSP

Misalkan saya diberi satu set terbatas poin di pesawat, dan diminta untuk menggambar kurva C ( P ) yang dapat dibedakan dua kali melalui p i , sedemikian sehingga perimeternya sekecil mungkin. Dengan asumsi p i = ( x i , y i ) dan x i < x i + 1 , saya dapat memformalkan masalah ini sebagai:$p_1,p_2,..p_n$$C(P)$$p_i$$p_i=(x_i,y_i)$$x_i<x_{i+1}$

Soal 1 (diedit sebagai respons terhadap komentar Suresh) Tentukan fungsi x ( t ) , y ( t ) dari parameter t sedemikian rupa sehingga arclength L = ∫ [ t ∈ 0 , 1 ] $C^2$$x(t),y(t)$$t$ diminimalkan, denganx(0)=x1,x(1)=xndan untuk semuati:x(ti)=xi, kita memilikiy(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)$

Bagaimana saya membuktikan (atau mungkin menyangkal) bahwa Masalah 1 adalah NP-keras?

Mengapa saya curiga kekerasan NP Misalkan asumsi santai. Jelas, fungsi minimum arclength adalah tur keliling Salesman dari p i 's. Mungkin kendala C 2 hanya membuat masalah lebih sulit?$C^2$$p_i$$C^2$

Konteks Varian dari masalah ini telah diposting di MSE . Itu tidak menerima jawaban di sana dan di MO . Mengingat bahwa tidak masalah untuk menyelesaikan masalah, saya ingin mengetahui seberapa sulitnya.

$\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)}]$lebih pendek, karena untuk setiap segmen garis lurus lebih pendek daripada kurva lain yang menghubungkan titik. Jadi untuk setiap pemesanan poin, kurva terbaik adalah solusi TSP, dan solusi TSP memberikan pemesanan poin terbaik.

$\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}$