2
$\begingroup$

Turing machines and neural networks are equivalent in their expressive powers, but as models of computation they are different. Turing machines come pre-configured with their transition functions while the neural networks configure weights to build learnable computable functions using input data.

Is the class of problems efficiently solvable by a neural network equivalent to the class P or NP... or some normal complexity class or do they have their own complexity classes that are not equivalent to normal ones.

$\endgroup$
9
  • 1
    $\begingroup$ Turing machines and neural networks are equivalent in their expressive powers – in what sense? A neural network has a fixed number of inputs. $\endgroup$ – Yuval Filmus Apr 22 '20 at 20:18
  • 1
    $\begingroup$ What does it mean for a problem to be efficiently solvable by a neural network? $\endgroup$ – Yuval Filmus Apr 22 '20 at 20:18
  • $\begingroup$ a particular instance of a neural network has a fixed number of inputs but I was speaking more about neural networks in general as models of computation like Neural Turing machines NTMs. but I understand your point. $\endgroup$ – DeeDee Apr 23 '20 at 1:01
  • $\begingroup$ expressive power might not be the right word. but I heard RNN's are Turing complete (apparently not in any practical sense tho). $\endgroup$ – DeeDee Apr 23 '20 at 1:05
  • $\begingroup$ still sounds totally possible to define sets of strings that are hard for neural networks to guess the rule (grammar) behind and others that are easy. and maybe hard and easy varies a little bit for different types of networks. you could say how accurate the network has to be and then define everything based on that. it has to get the rule right for an exponential number of future examples it sees in the number of examples it has already seen. idk. there has to be fun stuff there. something along these lines $\endgroup$ – DeeDee Apr 23 '20 at 1:15
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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