1
$\begingroup$

From this video lecture from MIT https://youtu.be/moPtwq_cVH8?t=1229 there is mention how NP complexity works with finding a "lucky" algorithm and luck can never be accounted for. The example he draws on is just seeking the next yes till you find some final output. For those reasons, I had assumed that even SGD is NP complex, and by extension Neural Networks. And my logic was that, through readings it seems like a Back Prop algorithm is always looking for a way to reach towards the global minima by taking the most negative step.

However, from my reading, it seems like Neural Networks have a computational Complexity of P. And as a result of the fact that most people believe $P\neq NP$ then a NN can only take a guess/approximation at a solution.

From what I follow, the belief is that since a Neural Network can't promise an ideal result, it isn't an NP solver. But that confuses me since from what I have seen, a Neural Network just never gives that ideal solution. Does that mean all these problems are just more complex than P and so they can only make a different guess every time? While an NP solution is supposed to consistently give back the correct answer.

From linear Algebra, we know that a solution needs to be a repeatable, deterministic mapping from $X\to Y$ Or else it is a mere approximation function and $X$ is not in the domain of the transformation.

To me that means either my understanding of what a Neural Network does in its backpropagation is wrong. Or that my understanding of NP complexity is wrong.

$\endgroup$
6
  • 3
    $\begingroup$ How do I make a neural net that can accept problem specifications of arbitrarily large size? If a particular neural net can only accept problem specifications smaller than some bound, then (1) a perfect NN NP-solver is no more impressive than table lookup and (2) P/NP don't enter into discussion. $\endgroup$ Sep 18, 2020 at 23:27
  • 1
    $\begingroup$ There may be a polynomial-time algorithm to evalute a neural network, but if your network requires an exponential (in the size of the input) number of nodes, then using the neural network is not a polynomial-time algorithm for solving your optimization problem. $\endgroup$
    – chepner
    Sep 19, 2020 at 14:44
  • 1
    $\begingroup$ (Also, strictly speaking, P and NP are classes of decision problems. If you have an upper bound on the value of an optimization problem, you can reduce it to a number of decision problems using binary search on the range of possible solutions. "Is there a solution with value <= K? Yes. Is there a value with solution <= K/2? No. Is there a value with solution between K/2 and 3K/4? Yes. And so on, until you find your optimal solution.) $\endgroup$
    – chepner
    Sep 19, 2020 at 14:46
  • $\begingroup$ NP complexity means polynomial time if your algorithm gets lucky when it runs. A neural net gets lucky when it creates an algorithm, and the algorithm does not get lucky when it runs. $\endgroup$
    – user253751
    Sep 20, 2020 at 11:51
  • $\begingroup$ @EricTowers: Recurrent neural networks take input sequences, generally of unbounded length. $\endgroup$
    – MSalters
    Sep 21, 2020 at 8:06

7 Answers 7

29
$\begingroup$

SGD is an algorithm, not a problem. It is not NP-complete or NP-hard. SGD is one approach to an optimization problem. Some optimization problems are NP-hard; some are not.

All of your deductions start from that one incorrect assumption, so they don't actually follow.

"Neural Networks" don't have a computational complexity; they aren't a problem.

$\endgroup$
3
  • $\begingroup$ Thank you for this. I had been doing some of my own reading work after asking my question and am arriving at similar answers. The first thing I realised is that a Neural Network, once trained is just a deterministic function. As a result of which, it can't be an algorithm used to solve an NP problem, since they have non-deterministic solutions from what I have read.(Usage of Luck). Apart from that, like you said, the clarity of what the terms mean makes sense. They talk about a problem and its solvability. Not about an algorithm on its own. $\endgroup$ Sep 18, 2020 at 8:28
  • $\begingroup$ I will try to figure out the difference between an optimization problem and an optimization algorithm moving forward. $\endgroup$ Sep 18, 2020 at 8:29
  • 5
    $\begingroup$ @Mr.JohnnyDoe Not sure if you implied but omitted that, but in case there is some misunderstanding: there is nothing "lucky" or non-deterministic about solution to NP problems. It's only that they have polynomial complexity only (if P!=NP) on nondeterministic Turing machine. $\endgroup$
    – Dan M.
    Sep 18, 2020 at 15:47
11
$\begingroup$

Let me start by briefly reviewing the kind of problems under discussion:

  • Problems in P: These are decision problems (where the answer is Yes or No), optimization problems (where the answer is an optimal solution to a problem such as minimum spanning tree), or function problems (compute some function of the input) which can be solved efficiently (in a certain exact sense) on all instances.

  • Problems in NP: You should not be troubled with the definition of these. Let me just suggest that you ignore the remarks on the MIT video. If you want to know what NP problems are, pick up a textbook on complexity theory.

  • NP-complete problems: The hardest problems in NP. For example, deciding whether a graph is Hamiltonian (contains a cycle visiting each vertex exactly once). Another example, finding a TSP tour of minimum cost. Most researchers conjecture that NP-complete problems cannot be solved efficiently on all instances, and so do not belong to P. There is a vast collection of NP-complete problems, and it is known that if one of them can be solved efficiently, then all of them can.

  • Learning problems: Let me describe the simplest setting, two class supervised learning, with an example. An algorithm is given a collection of pictures of cats and dogs, each one annotated by one of these two classes. The goal is to construct a "learner" algorithm, which will later on be able to classify new cats and dogs with a small probability of failure.

Neural networks are a certain kind of learner that can be constructed by a learning algorithm. Nowadays, most of these learning algorithms employ stochastic gradient descent, which involves backpropagation. Some neural networks accept inputs of a fixed size, others (for example, RNNs) accept an input stream.

As you can see, neural networks do not really fit into the P vs NP framework. They solve a "learning problem" rather than a decision problem or an optimization problem. People have tried solving NP-complete problems using neural networks, with some success, but this has no bearing on the P vs NP issue, for several reasons:

  • The neural networks involved have a fixed input size. Perhaps it all breaks down for larger input sizes.
  • The neural networks make mistakes, whereas P vs NP is about efficient algorithms that solve all instances of NP-complete problems.

In fact, it is already known that some NP-complete problems are feasible on real-world instances (check, for example, the areas of SAT solving and Integer programming).


If you want to understand these issues more (and to avoid stating claims such as "SGD is NP-complete", which do not make much sense), you would have to roll up your sleeves and get more technical. The MIT lecturer is painting a nice picture when they are discussing "luck", and people who are already familiar with NP might be able to understand how this corresponds to the actual definition of NP, but for anybody else, such descriptions are at best misleading.

Stochastic gradient descent (which is implemented efficiently via backpropagation) is a variant of gradient descent, which is a standard algorithm in continuous optimization. The corresponding algorithmic technique in combinatorial optimization is the greedy heuristic, which demonstrably fails on many NP-complete problems (though in some cases, results in the best worst-case approximation ratios).

Despite the mental picture suggested by the MIT video, stochastic gradient descent is not a universal solver for NP problems. In order to understand why, I will have to explain a bit more about NP problems, using examples:

  • NP decision problems: Consider the problem of deciding whether a graph contains a Hamiltonian cycle. Given just a graph, it might be hard to find such a cycle. But given a graph and a Hamiltonian cycle, it is easy to verify that the graph is indeed Hamiltonian (by checking that it contains the given cycle). It is conjectured that no such "witness" exists for non-Hamiltonicity.

  • NP optimization problems: Consider TSP, which is the analog of Hamiltonicity for weighted graphs: the goal now is to find a Hamiltonian cycle with smallest total weight. We can verify that the optimal cost is at most $W$ given a Hamiltonian cycle of total weight at most $W$. This is what it means for this optimization problem to be in NP.

Stochastic gradient descent is a continuous optimization algorithm which attempts (in this case) to find weights for the neural networks which minimize the number of errors that the network makes on the test instances. In many cases, there is also a regularization factor which pushes the weights down. Minimizing this cost function is NP-complete in general, but much of machine learning involves avoiding this worst case by "changing the problem" until it becomes feasible.

From the perspective of learning theory, more is happening here. We are interested not only in the training error (the error on training instances), but also in the generalization error (the error on new instances). Stochastic gradient descent continues minimizing the generalization error even after it has minimized the empirical error – it is not completely understood why (though many researchers have come up with partial explanations, often rejected by other researchers).

Getting back to the issue of stochastic gradient descent as a universal algorithm, one can view stochastic gradient descent as solving an NP-complete optimization problem. But there are several issues with this:

  • The optimization angle is only part of the picture. Generalization is as important.
  • Stochastic gradient descent doesn't always succeed. It doesn't solve all instances of the optimization problem it sets out to solve (minimize the training error).

There are other "universal algorithms" which appear to solve many NP-complete problems en masse, namely the ones used for SAT solving (and now, QBF solving) and integer programming. In these cases, it is easy to come up with explicit instances which are provably hard for all such algorithms. The case of stochastic gradient descent is more complicated due to the issues mentioned above, but it is also no panacea.


Finally, you mention that neural networks have a complexity of P. This is certainly true in some senses. For example:

  • Evaluating a neural network is in P. However, finding good weights seems to be hard. Similarly, finding a Hamiltonian cycle is difficult, but verifying that a given cycle is Hamiltonian is easy.

  • Running one step of stochastic gradient descent is in P (modulo the stochastic part!). However, we might have to run many steps of stochastic gradient descent, making the entire training process inefficient.

As you can see, this has no bearing on the capabilities of neural networks.

$\endgroup$
6
  • $\begingroup$ thank you so much for your answer. It really makes a lot os sense. With the first part, I get it now. The whole conversation of "P or NP?" comes down the ability of a problem being solved in a way that says "I am sure I know what the problem was and i know this is the best answer". So you should be able to say "I know that this is a hamiltonian cycle" or "This is the least time a travelling salesman would take." $\endgroup$ Sep 18, 2020 at 9:10
  • $\begingroup$ A Neural Network just isn't looking to solve those problems, and maybe aren't capable of solving them yet. The best they can do is learn a representation and give you a confidence score. Which is obviously very different from what comes into the domain of questioning brought about for P v NP problems. Plus, from what I know we can't verify correctness the same way for a Neural Network. We can't take that same input and say "huh, I guess that class label was right." Since they are trained differently $\endgroup$ Sep 18, 2020 at 9:12
  • $\begingroup$ What really drove the difference home was looking at a Sudoku. With NP solving, you want to find that solution and then verify it in polynomial time. With a NN, I just don't see that happening. The best I could do is ask "Can I solve this?" and then take a training set and make a guess if it can be done or not. Essentially, since the NN network isn't doing the same things. It can't be seen with the same metrics. It can approximate a decent solution and that is it. I found it a little counter intuitive that it uses optimization but isn't the same type of tool as P v NP $\endgroup$ Sep 18, 2020 at 9:13
  • 1
    $\begingroup$ @Mr.JohnnyDoe Your Sudoku puzzle distinction isn't great here. Efficiently being to answer "Can I solve this Sudoku puzzle" implies efficiently being able to find a solution via a "standard" technique --- Start with the Sudoku puzzle (say with $k$ unfilled slots, note that $k$ is at most the size of the board, which is some small polynomial in $n$). For each slot, do the following: Try filling in the slot with 1, then asking if it's solvable. If yes, go to the next slot, if no, try filling in the slot with 2, etc. This solves the search problem with at most $kn$ calls to the decision oracle. $\endgroup$ Sep 18, 2020 at 17:44
  • 1
    $\begingroup$ @Mr.JohnnyDoe Note that while this example may seem like "trying all the possible values", it isn't in am important way. For each slot, we may have to set that slot in isolation to each possible value (which would mean $nk$ total cases to consider). Trying to "brute force" it without a decision oracle would instead (if doing it naively) involve setting all possible simultaneously to some variable. There are $O(n^k)$ ways of doing this (you can probably decrease it some by using the rules of Sudoku), which if $k$ is a polynomial in $n$ is exponential in $n$. $\endgroup$ Sep 18, 2020 at 17:47
5
$\begingroup$

Non-linear optimization in general is not in NP, it isn't solvable at all. You cannot check in polynomial time whether a solution is the global optimum or just a local one. There is, in fact, no way to tell if your optimum is global, other than finding all of them (How would that work, how do you know how many optimums there should be, and what do you do if no global optimum exists, just infinitely many local ones?)

Backpropagation, SGD and any other optimization algorithm can't promise that they actually have found the global optimum. They can only promise a local optimum.

By the way: What problems a NN can solve (after it is trained) is independent on how its parameters were learned. If we look at a specific NN, we could say computing the output from the input is in O(1) because there are a fixed set of calculations that is done for any input. But that only makes moderate sense because the input size is also fixed for a specific NN.

$\endgroup$
4
  • $\begingroup$ > Non-linear optimization in general is not in NP, it isn't solvable at all I like that wording. It makes sense, Maybe in most cases a global minma doesn't exist or can't be found? I am not sure I know which it is. And about the last two points. I think those make a lot of sense to me. A backpropogation doesn't guarantee a correct mapping/global minima. As a result, using Back Prop is an approximation and not a solution. $\endgroup$ Sep 18, 2020 at 8:38
  • $\begingroup$ Going into a NN, that makes sense too, I was reading a Medium Article That pointed out how at the end of the day, a fully trained Neural Network is just a deterministic function that was found with the help of some stochastic tools. As a result, such a model can't solve an NP problem, since it is deterministic. And even then, a small subset of problems might have distributions tracable by a Network $\endgroup$ Sep 18, 2020 at 8:39
  • $\begingroup$ @Mr.JohnnyDoe I added a little bit to make it clearer that not only can't you check whether the minimum is global in polynomial time, you can't really check it at all. Is that still fine? Should be, right? $\endgroup$
    – kutschkem
    Sep 18, 2020 at 11:55
  • $\begingroup$ @Mr.JohnnyDoe note that if a global minimum doesn't exist, that means you can get better and better solutions, and if you had an algorithm where you tell it how good of a solution you want and it gives you one, then we'd probably consider the problem "solved" even though it doesn't find a global minimum. $\endgroup$
    – user253751
    Sep 21, 2020 at 10:33
4
$\begingroup$

Neural networks work reasonably well solving some kinds of problems. They are also awfully bad at solving other problems that they are used for.

Neural networks are totally incapable of solving NP complete problems beyond cases that can be solved by brute force, and not very good at this. There are optimisation problems where finding a good solution is possible even though finding an optimal solution is NP-complete, that’s the only area where neural networks might help.

The strength of neural networks is to detect patterns, especially small patterns. Now take a problem like “divide a set of integers into two subsets whose sums are equal or as close together as possible”. There are no patterns. If you change one number in a set, the other numbers change completely. There’s no pattern.

$\endgroup$
1
  • $\begingroup$ This actually makes a lot of sense.I had taken some time out to read about these concepts and what you mention is becoming rather clear to me. NNs are just a tool that try to solve an optimisation. That could mean correct class labels or anything else. But they aren't the problem, they are just the tool. The problem would be the optimization of distributions and mapping input to output class labels. In some cases where a problem might be simple, a network might yield some good accuracy. But it doesn't quite solve the problem. It just finds a passable approximation. $\endgroup$ Sep 18, 2020 at 8:35
4
$\begingroup$

I think it is worthwhile to expand upon the “lucky guess” in reference to NP problems. That is a reference to the fact that NP problems are easy to verify. Instead of the typical factoring primes, let’s go with with a more down to earth problem. Say the year is 1970 and you want to know if there is a company that has 2 employees, one named Bob, one named Alice, who do not work in the same department, but both work primarily with numbers and they do know each other’s work phone number’s. How do you solve this problem quickly and easily? Today, you might be able to solve this problem through scanning online profiles, but in 1970 it would be different. It might be impossible to solve if the answer is no, but if the answer is yes, and you know the answer, it is trivial to verify, especially if the answer includes their numbers (simply pick up the phone, make two phone calls, done).

Now, if you were the “lucky guesser”, you could solve that problem nearly as quickly as you could verify it, you’d pick up the phone and call a company, and ask to speak to the operator, you’d ask for the number of Alice, they say they are a big company and have 150 Alice’s, which one do you want, and you’d say you’d like the number of Alice N, and they give you a number, you then ask for Bob, get told there are 163 Bob’s, you ask for and get Bob P’s number. One conference call later and you’re done.

A neural net may be able to solve your NP problem through brute force, it might be able to identify factors that dramatically reduce the search space so that the problem is smaller than you first thought. But it’s not going to be a lucky guesser, and it is unlikely to come up with step by step instructions that would allow you to solve the problem as quickly as the lucky guesser.

Neural nets frequently come up with precise answers, but they don’t do so by developing new algorithms. Which is what you’d need to do for P=NP.

$\endgroup$
4
  • $\begingroup$ I don’t think this is a good argument. NP complete problems are problems that we could solve efficiently by making lucky guesses, but we can’t make lucky guesses. Plus for decision problems with answer “No” we would need reliable lucky guesses. $\endgroup$
    – gnasher729
    Sep 21, 2020 at 8:50
  • 1
    $\begingroup$ If you were an NP lucky guesser you'd also dial a random number for the company and the first words off the top of your head would be Alice and Bob's surnames and departments :) $\endgroup$
    – user253751
    Sep 21, 2020 at 10:35
  • $\begingroup$ @user253751: I stretched it out, this is a slow and methodical lucky guesser. $\endgroup$
    – jmoreno
    Sep 21, 2020 at 11:04
  • $\begingroup$ @gnasher729: my point is that a neural net is not a lucky guesser, we can’t turn NP into P by throwing a NN at it. And the reason isn’t because the NN gives a fuzzy answer, or because we don’t know what what is being weighted to give that answer. It’s because NN looks for patterns, not algorithms, and a lucky guesser does neither. $\endgroup$
    – jmoreno
    Sep 27, 2020 at 17:29
2
$\begingroup$

It seems like the OP is asking "what class of problems can be solved by a neural network"? It turns out that we have an answer.

First, realize that neural networks are "function approximators". In other words, a neural network is itself a function $\hat{f}$, which has been "trained" to mimic some function $f$ that we have sampled. The set of samples is the "training set", and an optimizer like SGD is used to minimize the "distance" between $f$ and $\hat{f}$ over the training set. The hope is that the learned function $\hat{f}$ will generalize. I.e. we hope that $f\approx \hat{f}$ outside of the training set as well.

Thus, when we ask about the "kinds of problems" which can be solved by neural networks, we really mean "which functions can they approximate?" Can neural networks be used to approximate any function? If not, what class of functions can neural networks approximate?

The answer to this question is given in the paper Multilayer Feedforward Neural Networks are Universal Approximators. The paper

rigorously establishes that standard multilayer feedforward networks with as few as one hidden layer using arbitrary squashing functions are capable of approximating any Borel measurable function from one finite dimensional space to another to any desired degree of accuracy, provided sufficiently many hidden units are available.

A precise definition of a "Borel measurable function" is given here. A more thorough discussion will be given in any text on Measure Theory.

This type of result is an known as a Universal Approximation Theorem. For another example, see here.

$\endgroup$
1
  • $\begingroup$ (I don't consider it useful to answer questions that were not asked, but should have been. For one thing, answers are found perusing question titles.) $\endgroup$
    – greybeard
    Sep 21, 2020 at 7:02
0
$\begingroup$

The other answers are correct, but to maybe add an intuitive perspective, you could imagine a neural network like a human brain, in terms of NP problem solving capabilities.

Both humans and neural networks are capable of "solving" hard problems "efficiently". One distinction I want to make to what has been previously discussed here is what constitutes "solving" with a neural network. I would say that optimizing the network parameters (backprop, SGD) is more similar to coming up with an algorithm to solve a problem, and the actual solving happens at inference time, not during training.

Humans have the advantage of using heuristics to come up with solutions, as do neural networks. For instance if we take some modern multiplayer game (many games are NP hard), we could observe that neural networks and humans are better at playing the game than a computer with a classical algorithm is. You can see that bots (computer controlled players), following a classical handcrafted algorithm, are worse than any decent player. For some of these games, such as DotA 2 or StarCraft II, we even have neural networks that easily beat any bot as well. In other words, a neural network algorithm is superior to a classical algorithm. Perhaps so much so that it is in a lower class than NP?

The answer has to be no, to maintain $P\neq NP$, but why? If we vaguely equivalate "solving" an NP hard problem as winning such a game, then the network is indeed very "fast", even in terms of computational complexity. However, in this view, winning a game is perhaps more similar to making a lucky guess, but not actually solving the problem. Solving the problem would mean you could theoretically make statements such as: Given the starting parameters of both teams in the game (e.g. heroes, items, skills), who wins, if everyone plays perfectly? Or even for any particular state of the game, you could tell who will win with perfect play. Having such knowledge by the way would trivially make you an extremely good player (only being limited by things like dexterity).

A neural network may be a fast NP solver in the sense that it is a fast algorithm, but within its complexity class, that is larger than polynomial. Even for problems that are NP hard, we sometimes do have to come up with fast algorithms to solve them, even when we know there is no polynomial complexity algorithm for that. I would say neural networks have a place in this area, however it would be really hard to prove that they actually solve the problem, even when we have a lot of experimental evidence that they understand/capture the problem well. So in that sense, you could call them "solvers", for which we cannot actually prove (yet) that they do solve the problems. But that might be an acceptable trade-off to make, in face of a problem where computation time does not allow for traditional algorithms to succeed.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. The Bit about Dota really ties it together for me. The main thing from what I understand is for NP you need a proper algorithm you can understand and then backtrack on. One that gives a solution. With a NN, we can't really see what those questions and answers and processes are. Why was a Carry picked last, why that carry, why those lanes. It is a mere guess that seems to work well. It is a mere guess that seems to work and we can't do more than appreciate our guesswork $\endgroup$ Sep 27, 2020 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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