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.