Can neural networks efficiently solve the traveling salesmen problem? Are there any research papers that show that neural networks can solve the TSP efficiently?
The TSP is an NP-hard problem, so I suspect that there are only approximate solutions to this problem, even with neural networks. So, in this case, how would efficiency be defined?
In this context, it seems that the time efficiency may be obtained by resource inefficiency: by making the neural network enormous and simulating all the possible worlds, then maximizing. So, while time to compute doesn't grow much as the problem grows, the size of the physical computer grows enormously for larger problems; how fast it computes is then, it seems to me, not a good measure of the efficiency of the algorithm in the common meaning of efficiency. In this case, the resources themselves only grow as fast as the problem size, but what explodes is the number of connections that must be built. If we go from 1000 to 2000 neurons to solve a problem twice as large and requiring exponentially as much time to solve, the algorithms requiring only twice as many neurons to solve in polynomial time seem efficient, but, really, there is still an enormous increase in connections and coefficients that need be built for this to work.
Is my above reasoning incorrect?