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.

Improve this question
$\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
    Commented Apr 22, 2020 at 20:18
  • 1
    $\begingroup$ What does it mean for a problem to be efficiently solvable by a neural network? $\endgroup$
    – Yuval Filmus
    Commented Apr 22, 2020 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
    Commented Apr 23, 2020 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
    Commented Apr 23, 2020 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
    Commented Apr 23, 2020 at 1:15

2 Answers 2

Reset to default
3
$\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.

Improve this answer
$\endgroup$
-2
$\begingroup$

I think that this reply never consider a fact,which the classical alogorithms and the human thought are constantly evolving with the abstraction and resolve of problem. Basicaly,I think effectively corresponding relationship between the concept of computational complexity and the concept of human cognition will clear the problem. Then,will figure that the effective apparent comparison Angle is not so simple.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Commented Dec 28, 2023 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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