10
$\begingroup$

I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. They use genetic algorithms to "evolve" the weights of the axons.

So basically my idea is the following. If I was supposed to write a program that recognizes numbers I would not know how to start (I could have some vague idea but my point is: It is not trivial, nor easy.) but by using neural network I do not have to. By creating the right context in order for the neural network to evolve, my neural network will "find the correct algorithm". Down below I quoted a really interesting part of the article where they explain how each layer have different role in the process of image recognition.

One of the challenges of neural networks is understanding what exactly goes on at each layer. We know that after training, each layer progressively extracts higher and higher-level features of the image, until the final layer essentially makes a decision on what the image shows. For example, the first layer maybe looks for edges or corners. Intermediate layers interpret the basic features to look for overall shapes or components, like a door or a leaf. The final few layers assemble those into complete interpretations—these neurons activate in response to very complex things such as entire buildings or trees.

So basically my question is the following: Couldn't we use genetic algorithms + neural networks in order to solve every NP problem? We just create the right evolutionary context and leave "nature" find a solution.

Inceptionism: Going Deeper into Neural Networks

EDIT: I know we can use Brute-Force or find a not-efficient solution in many cases. That is why I try to highlight Evolving artificial neural networks. As I said in a comment: Given sufficient time and an appropriate mutation rate we could find the optimal solution (Or at least that is what I think).

Concept

$\endgroup$
  • 1
    $\begingroup$ We don't have to. We can simply use brute-force. What is your goal, exactly? $\endgroup$ – Pål GD Sep 23 '15 at 15:23
  • 2
    $\begingroup$ I am not an expert on neural networks so I don't know if they can be trained to solve NP problems correctly. But I don't think you are asking the right question. Coming up with an algorithm that solves a problem contained in NP is usually not difficult, just check every possible solution. However, finding an algorithm that solves an NP-hard problem in polynomial time is a different story and its existence is highly unlikely. Since neural networks can be simulated by a truing machine, they still need super polynomial time unless P=NP and won't be of much help. $\endgroup$ – Dennis Kraft Sep 23 '15 at 15:23
  • $\begingroup$ yes, neural nets have been used against NP complete problems eg Travelling Salesman and many others and there is research/ literature on the subj. they can have some useful properties but they dont get away from time constraints of complexity theory as DK points out. $\endgroup$ – vzn Sep 23 '15 at 15:54
  • $\begingroup$ My point is: Using an appropiate mutation rate and sufficient time we could (at least theorically) find the optimal solution. (Or at least a local maximum) Image: Concept $\endgroup$ – NMO Sep 23 '15 at 16:21
  • 1
    $\begingroup$ Genetic algorithms (and the rest of the lot of "AI" techniques) are essentially randomized "try a sample of the solution space" with some smarts (heuristics) thrown in to make it not totally random. No, it is not better than "try all possible solutions", most of the time much worse (as there is no guarantee not to check the same discarded case again). Sure, they find "decent" solutions. But we want to find the best. $\endgroup$ – vonbrand Sep 24 '15 at 1:13
19
$\begingroup$

No. This direction is unlikely to be useful, for two reasons:

  1. Most computer scientists believe that P $\ne$ NP. Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to solve any NP-complete problem. If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the neural network will itself be a polynomial-time algorithm. It follows that if P $\ne$ NP, neural networks cannot efficiently solve any NP-complete problem.

  2. Neural networks aren't "magic". They are a way of trying to find patterns. For some problems where there are strong enough patterns to be found, and the patterns can be learned from a reasonable number of examples, they might be effective. But they're not magic fairy dust. Just because you can set up a neural network doesn't mean that backpropagation will necessarily find a good way to solve your problem. It might be that there are no patterns to be found, that the patterns can only be discovered with an unfeasible number of examples, or that patterns exist but the neural network training procedure isn't able to find them.

Neural networks are just another form of machine learning. We could make the same remarks about SVMs or random forests or linear regression any other form of machine learning. Neural networks aren't some kind of magical silver bullet that solve all machine learning problems. They're about as effective as other machine learning methods, or for some kinds of problems, maybe a little bit more effective, but they're not magic.

Sometimes I run across people who have heard only a little bit about neural networks, and they walk away thinking that neural networks are the answer to everything -- maybe because they heard that "your brain uses neural networks too", or they saw some very cool application (voice recognition or something). But don't be fooled. Don't believe the hype. Neural networks are a useful technique, but they're not going to enable computers to solve NP-complete problems, or to beat the Turing test, take away all our jobs and replace humans with computers. Not anytime soon, anyway. That's just science fiction.

$\endgroup$
  • 1
    $\begingroup$ Really good answer. Genetic Algorithms + Neural Networks seems very powerful but maybe it is not enough to solve every np problem. I imagine leaving this neural networks + genetic algorithms in the wild looking for this p solutions. Like little scouts haha. $\endgroup$ – NMO Sep 23 '15 at 17:05
  • $\begingroup$ May also be worth noting that neural networks typically provide some probability of finding the correct answer, not a guarantee. When you relax your problem requirements to allow sub-optimal solutions, there are very often practical solutions to NP-complete problems, despite their intractability in the worst case. $\endgroup$ – Dan Bryant Sep 23 '15 at 20:39
8
$\begingroup$

It seems other answers while informative/ helpful are not actually understanding your question exactly and are reading a little too much into it. You didn't ask if neural networks would outperform other methods, you only asked if they could be applied to NP complete problems. The answer is yes, with some success and this has been known for decades and there is a wide variety of research on this, and it continues. This has to do with the flexibility of machine learning. Note that even if they dont find exact or optimal solutions, the solutions they have may have other desirable properties. some example papers:

$\endgroup$
4
$\begingroup$

Neural networks do not actually solve NP-complete problems. What they do do is solve problems which are remarkably close to NP-complete problems.

One big feature of neural networks is that they are not obliged to find the "right" answer every time. They are allowed to be "wrong." For example, you might be solving a bin-packing problem, and come to a solution which is 1% off of the ideal solution and be totally content with that answer.

If you remove the requirement of being 100% right every time, other problem solving approaches work very well. For example, many route planning algorithms (a la Google Maps) have to be NP-complete, but it is quite trivial to find an algorithm which finds a path within 1% of the optimum 99.9% of the time. It's trying to pin down results in that last 0.1% of the cases which drive NP-complete efforts to be so mindnumbingly expensive.

As it happens, when we try to use NP-complete equations in real life, we don't often need the actual answer. We're often very comfortable with a "close" answer, though we often don't have a wording to explain what "close" metric we are using. These are the situations where a neural network can answer the actual question you wanted to ask, rather than having to actually solve the NP-complete problem you asked for instead.

$\endgroup$

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.