Why can't we say that a Neural Network is a NP problem solver?
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.