Why can't we say that a Neural Network is a NP problem solver? From this video lecture from MIT https://youtu.be/moPtwq_cVH8?t=1229 there is mention how NP complexity works with finding a &quot;lucky&quot; 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.
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.
&quot;Neural Networks&quot; don't have a computational complexity; they aren't a problem.