Answers.Body: <p>There is some recent work addressing this issue, to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. See <a href="https://arxiv.org/pdf/1506.03134.pdf" rel="nofollow noreferrer">Pointer Networks</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-01T08:14:03.307Z
Answers.LastActivityDate: 2021-01-17T21:21:42.973Z
Answers.LastEditDate: 2021-01-17T21:21:42.973Z
Answers.UserDisplayName: Fadi Bakoura
Answers.Body: <p>To the best of my knowledge, there isn't any difference between the algorithmic methods and the NN methods. Those that can solve in polynomial time do not give a precise solution. Those that do give a precise solution do not solve in polynomial time. Of those that give a precise solution, the fastest takes <span class="math-container">$2^N$</span>, but it blows up in terms of memory. The fastest good algorithm I believe is <a href="https://en.wikipedia.org/wiki/Concorde_TSP_Solver" rel="nofollow noreferrer">Concorde</a>.</p>
  <p>The efficient algorithms solve in polynomial time, don't blow up in terms of memory, and give a solution close to perfect, say, within 2-3%. Again, to the best of my knowledge, no NN has beaten the best algorithmic solutions, but there are suggestions that some NN solution could be faster.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-04-01T00:34:15.560Z
Answers.LastActivityDate: 2021-01-17T21:21:09.960Z
Answers.LastEditDate: 2021-01-17T21:21:09.960Z
Answers.UserDisplayName: scientious
Body: <p>Can neural networks efficiently solve the traveling salesmen problem? Are there any research papers that show that neural networks can solve the TSP efficiently?</p>
  <p>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 <em>efficiency</em> be defined?</p>
  <p>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.</p>
  <p>Is my above reasoning incorrect?</p>
  
Tags: <neural-networks><reference-request><time-complexity><efficiency><travelling-salesman-problem>
Title: Can neural networks efficiently solve the traveling salesmen problem?
UserDisplayName: Gottfried William
ThreadText: # Can neural networks efficiently solve the traveling salesmen problem?
  
  (Asked by: username_0 on 2017-02-25)
  
  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?
  
  **Tags:** neural-networks, reference-request, time-complexity, efficiency, travelling-salesman-problem
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2018-04-01. Score: 2 | Accepted answer
  
  To the best of my knowledge, there isn't any difference between the algorithmic methods and the NN methods. Those that can solve in polynomial time do not give a precise solution. Those that do give a precise solution do not solve in polynomial time. Of those that give a precise solution, the fastest takes $2^N$, but it blows up in terms of memory. The fastest good algorithm I believe is [Concorde](https://en.wikipedia.org/wiki/Concorde_TSP_Solver).
  
  The efficient algorithms solve in polynomial time, don't blow up in terms of memory, and give a solution close to perfect, say, within 2-3%. Again, to the best of my knowledge, no NN has beaten the best algorithmic solutions, but there are suggestions that some NN solution could be faster.
  
  
  ---
  
  ### Answer by username_1 on 2018-05-01. Score: 2
  
  There is some recent work addressing this issue, to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. See [Pointer Networks](https://arxiv.org/pdf/1506.03134.pdf).
  
  
  ---
  
  