The question comes from the following scenario, assume we have the traveler problem which is NP (the one where a traveler wants to visit all countries with the lowest cost(by summing up all flights))

So basically Neural Network can not just predict, but generate results from things they've learned, for instance, training a network on various test cases of the aforementioned problem, after a proper training may result with the optimal result, something which is computationally finite, which happens on a computer, which can be imitated by a Turing Machine, and finally inferring that a problem which is considered NP falls into the category of P.

I would like to hear your thoughts of what point am I missing here

Some might say that because you're depending on a Gradient-Descent or so, you're already missing the optimum finding, but for me, it looks like the NN can actually learn the better paths and find an optimum. Although it sounds like maintaining several local-best spots in our search dimension but something tells me there's a difference here

  • $\begingroup$ What are you using for your definition of "NP"? $\endgroup$ Aug 29 '18 at 23:12
  • 1
    $\begingroup$ There are functions that are asymptotically greater than any polynomial but asymptotically less than any exponential, so there can be algorithms whose time complexity is P-hard but not EXP-hard. NP is not defined as not being EXP-hard. At any rate, even taking that as the definition, a given neural net can only correctly handle problem instances up to a finite size, so you can't make one NN to solve all TSP problems. If you intend to train different NNs for different TSP instances, then you have given no argument that the training produces a correct NN in less than exponential time. $\endgroup$ Aug 29 '18 at 23:40
  • 2
    $\begingroup$ @JeremyShiklov That is not the definition of NP. $\endgroup$ Aug 30 '18 at 6:12
  • 3
    $\begingroup$ @JeremyShiklov Yes, it matters hugely. You're claiming to have solved some problem using some method. If you don't even know what that problem is, there's no hope that your method is correct. And there are plenty of better-than-brute-force algorithms for NP-complete problems, so the thing you're claiming to be "the important part" isn't even a part at all. $\endgroup$ Aug 30 '18 at 9:22
  • 5
    $\begingroup$ I'm voting to close this question as off-topic because it is seeking validation of an attempt to solve the biggest open problem in computer science but incorrectly defines that problem. Thus, there is nothing to validate. $\endgroup$ Aug 30 '18 at 9:23

I would say that you are deeply overoptimistic about what "deep learning" can achieve. Mostly you are lucky if "deep learning" just manages to figure out something close to the rules of the game, like figuring out that a travelling salesman solution tends to be better if the visited towns are closer together.

Bit longer answer:

  1. If deep learning can solve NP-complete problems in polynomial time, then P = NP.
  2. Most people believe that P ≠ NP.
  3. Because of 1. and 2., most people who know little about deep learning assume that deep learning cannot solve NP-complete problems in polynomial time.
  4. When you look at what deep learning actually does, it is obvious that deep learning is nowhere near solving NP-complete problems in polynomial time or solving them at all.

Here's what deep learning can do: I give you the name of fifty cities and all kinds of information about them. Then I give you a million different permutations of the cities, and for each permutation a "cost". I tell the computer to find a permutation that minimises the cost. Deep learning examines all the data and tries to figure out what makes the cost high or low. And then it finds a permutation that should make the cost lowest, according to the analysis of cost.

Maybe it figures out, that the cost is based on the relative distances of cities. Maybe not. But if it finds out exactly what causes the cost, then it is just at a starting point.

  • $\begingroup$ but what is the mathematical contradiction here? $\endgroup$ Aug 30 '18 at 6:21
  • 3
    $\begingroup$ @JeremyShiklov Your question doesn't contain a mathematical argument to begin with. You're basically saying "Deep learning can solve TSP to optimality in polynomial time, so P=NP", but haven't established that deep learning can actually do that. Neural networks are not something that we have a really deep understanding of, they're basically a black box containing some random formulas that we shake in the hope it gives us a right answer. For some reason that answer ends up being good enough most of the time, but that isn't a mathematical proof it is always prefect all of the time (far from it). $\endgroup$ Aug 30 '18 at 10:27

First, it might take an exponential number of steps to find an optimal solution using NN algorithms. It might happen if you need train an exponential number of use cases to solve optimally particular instance, or that there are exponential number of improvements. Eventually, it will lead for an exponentially time algorithm.

Second, NN algorithms usually finds a local extreme point, rather than a global extreme point. In many problems (such as TSP for general graphs) a local extreme point is far from a global extreme point.

  • 1
    $\begingroup$ The fact that I need to teach the NN with an exponential number of use cases is more of an answer I was looking for. Thank you! $\endgroup$ Aug 30 '18 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.