I occasionally read papers that show neural networks solving traveling salesmen problems and multi traveling salesmen problems efficiently?
1) Is there any analysis of the meaning of efficiency of algorithms for networks that allowed to grow in size with the problem they are supposed to solve?
2) What are the earliest papers solving the TSP with NN this?
3) Is the meaning of efficiency used in these papers is the same as the usual one, in fact, and works only in this problem specifically?
These problems are NP hard. So I suspect I'm not sure what these papers mean by efficient.
The neural network postulated have a sufficiently vast number of interacting elements and in effect do the combinatorics strictly, for each special case. But if so, while this is fast and doesn't grow much with the size of the problem growing, is this really comparable to the normal meaning of PT as fast or efficient?
In these cases it seems the time efficiency is obtained by resource inefficiency: by making the 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 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 PT 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?