# Is Euclidean TSP strongly NP-hard

Is Euclidean TSP strongly NP-hard? What I mean is if it is NP-hard with weights specified in unary?

Can someone provide a reference?

• Weights are distances in Euclidean TSP, so I assume you mean that the coordinates are specified in unary. – Yuval Filmus Apr 12 '18 at 10:16
• @YuvalFilmus Yes, indeed! (Though I hadn't thought of it this way before). Is it still NP-hard? – mathstudent42 Apr 12 '18 at 12:49

And the required precision for the $L_0$ value in page 243 is to be able to distinguish between $a$ and ${(a^2+1)}^\frac12$. And near the end of page 241, he wrote "An adequate value of $a$ is 20." So the required precision is finite. Since you only have $n(4a + 13 + 2^\frac12)$, that would only magnify the difference.