What are some complexity classes for neural networks?
Basically, no one has proven anything useful about which tasks a neural networks are able to efficiently learn to solve.

What we can say is: they're not magic pixie dust.  They can't solve NP-complete problems in polynomial time, unless P = NP.

In practice, for most tasks that you'd find in a classical algorithms class, human-made algorithms vastly outperform neural networks.  The situations where neural networks are better tends to be tasks that don't admit a crisp problem statement or specification of the desired behavior.