I’m trying to research this. Am out of house currently.
Right now I fail to understand what’s non-deterministic about the TSP. Makes no sense. Equal input = equal output. Roads and cities don’t change “randomly” while trying to find the solution.
A non-deterministic solving-algorithm changing results for some reason … why should that make sense? It’s like adding a random, which is deterministic, or letting an AI come up with one, which is also deterministic but might change over time assuming it also learns. Still deterministic, though.
In the end there simply isn’t any problem which can’t be solved by piling enough specialized hardware on it, brute forcing a result, even if it requires the size of the moon… no?
This all sounds more and more like someone came up with an irrelevant problem fooling everyone into believing it matters. Purely theoretical with no base in reality… no?
Doctor V, @Valerie_Valate, said P is not NP!
Oh, my latest source:
Reading this now:
https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en