It’s indeed NP-complete if edge lengths are integers or otherwise discretized. But the general traveling salesman problem has no such restriction, so you can’t finitely enumerate in the general case.
In the general case, you just have a big list of edge weights, which means you have to be able to write the edge weights down.
If you want to represent the problem as a bunch of points in a Euclidean plane with free travel, that's a different (and easier) problem.
And even then, while it might take an infinite number of steps to specify the answer at infinite resolution, it will only take a finite number of steps to specify the answer at any level you're capable of writing down.
> it will only take a finite number of steps to specify the answer at any level you're capable of writing down.
That’s basically the good old “everything is O(1) because int64/float64 has 2^64 possibilities” misconception. It’s not how complexity theory works. For any N, 2^N is still finite, we’re obviously not talking about undecidable problems.
Edit: I see that you may be responding to the “finitely enumerate” part of my comment. Sure, it wasn’t phrased well. Replace with “enumerate in P”.
What are you fixing? Suppose you want to know the answer to within one part in 10¹⁰⁰. That will take you 333 questions.
Suppose you don't actually need 100 decimal places of the answer, or more likely that even if you had them you'd be unable to use them, and you can only represent the answer to 20 decimal places. That will take you 67 questions.
You can easily enumerate this answer in P. The problem in your argument isn't that float64 only has 2^64 values. Use as many bits to hold the answer as you want. No matter how many that is, it will be a finite number, and you'll be able to specify them all in a polynomial amount of time. Each question takes polynomial time to answer and fills one bit of the solution.
Okay apparently my complexity theory is rusty and I’m remembering results but not remembering the reasons for those results, so sorry about that. Determining optimal path length to a certain degree is indeed in the same class as the decision problem. It’s finding that optimal path (optimization problem) that’s not NP-complete.
> It’s finding that optimal path (optimization problem) that’s not NP-complete.
I'm having some trouble with this. As far as I can see, finding a path of a given maximum length must be in NP, because it's very easy to deterministically verify that a given path has length no more than the maximum.
If determining the optimal path length is in NP, and identifying a path of that length is also in NP, how can determining an optimal path fail to be in NP?
