# Is the Euclidean TSP weakly NP-hard?

So the Euclidean TSP decision problem is NP-complete (see http://dx.doi.org/10.1016/0304-3975(77)90012-3 ) so the TSP optimization problem should be NP-hard.

On the other hand there is a PTAS for the Euclidean TSP (see http://dx.doi.org/10.1145/290179.290180 ).

Wikipedia says that a PTAS is not possible for strongly NP-hard Problems.

So is this a contradiction, or is the Euclidean TSP "only" weakly NP-hard? Did I miss something else?

• – vzn Apr 30 '15 at 18:15
• Why would it be a contradiction? "Strongly NP-hard" is not the same concept as "NP-hard". – D.W. Apr 30 '15 at 21:11
• @D.W. Of course it is not. I just wanted to know where the failure in my understanding was. Maybe the question is not optimally formulated. – surt91 May 1 '15 at 15:39
• You could have PTAS for Strongly NP-hard Problem!!! But you cannot have FPTAS for Strongly NP-hard problem unless P=NP – user777 Mar 1 '18 at 10:09

You're confusing a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS). Euclidean TSP has a PTAS, but it is not an FPTAS because the polynomial increases in degree as 1 / ε decreases. Only an FPTAS is disallowed for strongly NP-hard problems, assuming P $\neq$ NP.