<p>According to this <a href="https://www.oreilly.com/ideas/the-hard-thing-about-deep-learning" rel="nofollow noreferrer">blog By Reza Zadeh</a>, training a neural network to produce correct output even for just two-thirds of the training examples is computationally hard:</p>
<blockquote>
<p>Indeed, in 1988 J. Stephen Judd shows the following problem to be NP-hard:</p>
<p>Given a general neural network and a set of training examples, does there exist a set of edge weights for the network so that the network produces the correct output for all the training examples?</p>
<p>Judd also shows that the problem remains NP-hard even if it only requires a network to produce the correct output for just two-thirds of the training examples, which implies that even approximately training a neural network is intrinsically difficult in the worst case. In 1993, Blum and Rivest make the news worse: even a simple network with just two layers and three nodes is NP-hard to train!</p>
</blockquote>

CC BY-SA 3.0
2017-12-11T10:11:41.543Z
I don't really see how this answers my question.
domotorp
CC BY-SA 3.0
2017-12-11T10:53:38.287Z
Before you edited the post, your first question is about training NN. Since you added the CC tag, my answer shows that it is hard to train NN regardless whether your Algorithmic problem is in P or NPC
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-12-11T12:44:58.623Z
I'm sorry if I was vague.
domotorp
CC BY-SA 3.0
2017-12-10T22:08:37.537Z
2017-12-10T22:08:37.537Z
2020-06-17T09:38:08.363Z
Mohammad Al-Turkistany
<p>It seems the answer must be positive, because what might a reasonable <em>negative</em> answer to &quot;Can neural networks be used to devise algorithms?&quot; look like? If you accept the premise that human brains are neural networks -- or at least can be modeled by such to a very high degree of accuracy -- doesn't that provide an existence proof? <em>We</em> can devise algorithms and therefore so can <em>some</em> neural net.</p>

CC BY-SA 4.0
2021-03-23T14:34:29.870Z
This is a good point, but I was hoping for something that we can build ourselves (without engaging in copulation).
domotorp
CC BY-SA 4.0
2021-03-23T14:54:58.477Z
I wasn’t suggesting that as a method of building such a network, merely pointing out an existence proof.
Aryeh
CC BY-SA 4.0
2021-03-23T23:19:40.683Z
This seems similar to (though perhaps somewhat less assertive than) the unpopular answer given by @FrancisHErdmanIII. Personally I think they're both good arguments.
Yonatan N
CC BY-SA 4.0
2021-03-24T21:16:42.293Z
Thanks! Admittedly, not a very deep cs-theoretic argument, but the way the question is phrased, it's very difficult to argue for a negative answer.
Aryeh
CC BY-SA 4.0
2021-03-23T09:35:24.827Z
2021-03-23T09:35:24.827Z
Aryeh
<p><strong>I am not an expert by any means, but I don't see why not, yet.</strong></p>

<p>Neural networks fundamentally perform <strong>optimization</strong> according to some sort of "cost/benefit model" that's often already known before-hand. Additionally, the search space is well-defined, with valid and invalid moves that are known, and "variations" that are easy to define. Even for AlphaZero and AlphaGo, the cost functions are probably based on win-rate and the resulting win-rates distribution for all possible moves after making a move, or some sort of heuristic for that.</p>

<p>For devising algorithms, you are essentially asking the program to learn how to output a correct string (with an implicit encoding and cost function already known) that corresponds to a program that "executes an algorithm." However, there are possibly infinitely many algorithms for which you an implement a program with. So perhaps you'll want to define the correct "fitness" metrics.</p>

<p>However, even for certain programs, "fitness" metrics can be somewhat hard to define. Time? Space usage? Quantification of "side effects?" Optimally, you'll generate "the shortest program" that does <em>only</em> what you want it to do.</p>

<p>I suppose that if you find the correct fitness metrics and adjustment algorithms, you'll be able to do this.</p>

CC BY-SA 3.0
2017-12-13T20:29:27.287Z
2017-12-13T20:29:27.287Z
CinchBlue
<p>"neural networks " transform a vector from one dimensional space to another dimensional space. so they are nothing more than highly , highly non-linear function approximators. even neural networks use approximation algorithms for their loss minimization . however training neural networks for devising new algorithms is out of question. tomas mikolov did some work in this area with stack augmented recurrent neural network , and i have also heard about "neural turing machines" for this domain. however finding optimal strategies has been the fundamental cause of studying reinforcement learning which is somewhat related to your question. but using neural networks for devising new algorithms is not possible , atleast in the near future.</p>

CC BY-SA 3.0
2017-12-10T20:42:15.410Z
I think an optimal strategy for a suitable game is the same as an optimal algorithm for the corresponding problem.
domotorp
CC BY-SA 3.0
2017-12-11T07:40:35.413Z
@domotorp "strategy" is more of a heuristic than an algorithm
thecomplexitytheorist
CC BY-SA 3.0
2017-12-10T17:27:44.437Z
2017-12-10T17:27:44.437Z
thecomplexitytheorist
<p>I am a QA Automation engineer so don't claim expertise at neural networks, but, tautologically, yes NN can themselves create algorithms. Humans themselves are NN at some level, and we create algorithms, so it stands to reason that artificial NN systems we create can themselves create algorithms. </p>

CC BY-SA 3.0
2017-12-10T15:45:12.457Z
2017-12-10T15:45:12.457Z
Francis H Erdman III
<p>This is not a full answer and I am not very experienced in neural nets, but perhaps helpful.</p>

<p>NNs essentially are given an input and produce a response. They are then trained via practice to produce similar responses on "similar" inputs in the domain, for example, the same label to images of the same animal, or high ratings to "good" chess positions where good means high winning chances.</p>

<p>So as I commented, neural nets are a non-uniform model of computation that work in a totally different way than step-by-step algorithms run on Turing Machines. Instead, think of them as "soft" circuits that use continuous math rather than Boolean and can be tweaked or trained, and are allowed to err.</p>

<blockquote>
  <p>Why is playing chess easier than Dijkstra or Graphisomorphism?</p>
</blockquote>

<p>Partially, it is the difference between asking someone to answer a question to the best of their ability, and asking them for the one correct answer along with a proof that it is correct. Partially, it is the difference between solving a fixed-size problem, and simultaneously solving the problem for all possible input sizes.</p>

<p>Each time Dijkstra's is run on an instance, which may be of any size, it implicitly <em>proves</em> that its output is the one true answer and no other. In chess and image recognition, one gives the best answer one can and errors are tolerated. Furthermore, one only trains networks to solve these problems of one size at a time. I don't think we know yet how to generalize such a neural net solution to, say, problem instances of entirely different sizes and shapes.</p>

<p>I don't think we should assume that neural nets <em>can't</em> solve shortest-paths or similar algorithmic problems, but they solve problems in a fundamentally different way than a step-by-step algorithm that is always correct.</p>

<p>Going back to the similarity between neural nets and circuits, note that circuits have been studied for decades, yet judging by <a href="https://cstheory.stackexchange.com/questions/23796/do-we-have-any-nontrivial-uniform-circuits">the lack of answers to (5) of my previous question</a>, we know almost nothing about how to construct fully correct circuits for a given problem except via transforming a uniform algorithm (Turing Machine) into a circuit.</p>

CC BY-SA 3.0
2017-12-11T20:13:05.820Z
I don't think having one answer makes a difference - two players can play Dijkstra by competing who can find a shorter path. Scalability might be a more serious issue - do you think NNs can learn how to play NIM?
domotorp
CC BY-SA 3.0
2017-12-11T23:49:58.520Z
@domotorp, I think there is a huge conceptual and practical difference between correct algorithms and incorrect but approximate heuristics. You didn't ask why chess is harder than approximate shortest paths, you asked why chess is harder than Dijkstra which is provably correct 100% of the time on all input sizes. Re: nim, no idea; you need a NN architecture that accepts arbitrarily large input to start with...
usul
CC BY-SA 3.0
2017-12-11T19:20:53.813Z
2017-12-11T19:20:53.813Z
usul
<p>After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I wondered whether</p>

<blockquote>
  <p>Can neural networks be trained to solve classic algorithmic problems?</p>
</blockquote>

<p>Here I mean that for example the network would get an input graph $G$ with weighted edges, and two vertices $s$ and $t$ specified, and we asked it to find a shortest $st$ path as fast as possible.
Then I guess the neural network would discover and train itself to use Dijkstra or something similar.</p>

<p>On one hand, we know that the <a href="https://cstheory.stackexchange.com/questions/2698/computational-power-of-neural-networks">computational power of neural networks is $TC^0$</a>.
On the other, I don't know if this is necessarily related to my question.
Even so, for most problems we don't know whether they can be solved in $TC^0$ or not.
Seeing whether a neural network can train itself, might be a good indicator whether there's a fast algorithm or not.
For example, if neural networks can't train themselves to solve SAT fast, then that makes it (even more) likely that $NP\not\subset TC^0$.
I wonder what a neural network would do with GRAPHISOMORPHISM or FACTORIZATION.</p>

<p>Of course, extracting the algorithm is a whole different question.
I suspect experts know how to do that, but discussing it is not the topic of this question.</p>

<p>Added two days later: After seeing the answers, let me specify that if you answer in the negative, then I would like to know</p>

<blockquote>
  <p>Why is playing chess easier than Dijkstra or Graphisomorphism?</p>
</blockquote>

CC BY-SA 3.0
2017-12-26T20:22:05.633Z
Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/70831/discussion-on-question-by-domotorp-can-neural-networks-be-used-to-devise-algorit).
Lev Reyzin
CC BY-SA 4.0
2021-03-23T20:29:23.157Z
Just pointing to a relevant paper: https://papers-gamma.link/paper/141
maxdan94
<cc.complexity-theory><ds.algorithms><machine-learning><ne.neural-evol>
Can neural networks be used to devise algorithms?
domotorp
# Can neural networks be used to devise algorithms?

(Asked by: username_0 on 2017-12-09)

After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I wondered whether

> Can neural networks be trained to solve classic algorithmic problems?

Here I mean that for example the network would get an input graph $G$ with weighted edges, and two vertices $s$ and $t$ specified, and we asked it to find a shortest $st$ path as fast as possible.
Then I guess the neural network would discover and train itself to use Dijkstra or something similar.

On one hand, we know that the [computational power of neural networks is $TC^0$](https://cstheory.stackexchange.com/questions/2698/computational-power-of-neural-networks).
On the other, I don't know if this is necessarily related to my question.
Even so, for most problems we don't know whether they can be solved in $TC^0$ or not.
Seeing whether a neural network can train itself, might be a good indicator whether there's a fast algorithm or not.
For example, if neural networks can't train themselves to solve SAT fast, then that makes it (even more) likely that $NP\not\subset TC^0$.
I wonder what a neural network would do with GRAPHISOMORPHISM or FACTORIZATION.

Of course, extracting the algorithm is a whole different question.
I suspect experts know how to do that, but discussing it is not the topic of this question.

Added two days later: After seeing the answers, let me specify that if you answer in the negative, then I would like to know

> Why is playing chess easier than Dijkstra or Graphisomorphism?

**Tags:** cc.complexity-theory, ds.algorithms, machine-learning, ne.neural-evol
> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/70831/discussion-on-question-by-domotorp-can-neural-networks-be-used-to-devise-algorit).  
> **username_2**: Just pointing to a relevant paper: https://papers-gamma.link/paper/141  

---

## 6 answers

### Answer by username_3 on 2017-12-10. Score: 3

According to this [blog By Reza Zadeh](https://www.oreilly.com/ideas/the-hard-thing-about-deep-learning), training a neural network to produce correct output even for just two-thirds of the training examples is computationally hard:

> Indeed, in 1988 J. Stephen Judd shows the following problem to be NP-hard:
>
> Given a general neural network and a set of training examples, does there exist a set of edge weights for the network so that the network produces the correct output for all the training examples?
>
> Judd also shows that the problem remains NP-hard even if it only requires a network to produce the correct output for just two-thirds of the training examples, which implies that even approximately training a neural network is intrinsically difficult in the worst case. In 1993, Blum and Rivest make the news worse: even a simple network with just two layers and three nodes is NP-hard to train!

> **Comments:**
> **username_0**: I don't really see how this answers my question.  
> **username_3**: Before you edited the post, your first question is about training NN. Since you added the CC tag, my answer shows that it is hard to train NN regardless whether your Algorithmic problem is in P or NPC  
> **username_0**: I'm sorry if I was vague.  

---

### Answer by username_4 on 2021-03-23. Score: 2

It seems the answer must be positive, because what might a reasonable *negative* answer to "Can neural networks be used to devise algorithms?" look like? If you accept the premise that human brains are neural networks -- or at least can be modeled by such to a very high degree of accuracy -- doesn't that provide an existence proof? *We* can devise algorithms and therefore so can *some* neural net.

> **Comments:**
> **username_0**: This is a good point, but I was hoping for something that we can build ourselves (without engaging in copulation).  
> **username_4**: I wasn’t suggesting that as a method of building such a network, merely pointing out an existence proof.  
> **username_5**: This seems similar to (though perhaps somewhat less assertive than) the unpopular answer given by @FrancisHErdmanIII. Personally I think they're both good arguments.  
> **username_4**: Thanks! Admittedly, not a very deep cs-theoretic argument, but the way the question is phrased, it's very difficult to argue for a negative answer.  

---

### Answer by username_6 on 2017-12-13. Score: 0

**I am not an expert by any means, but I don't see why not, yet.**

Neural networks fundamentally perform **optimization** according to some sort of "cost/benefit model" that's often already known before-hand. Additionally, the search space is well-defined, with valid and invalid moves that are known, and "variations" that are easy to define. Even for AlphaZero and AlphaGo, the cost functions are probably based on win-rate and the resulting win-rates distribution for all possible moves after making a move, or some sort of heuristic for that.

For devising algorithms, you are essentially asking the program to learn how to output a correct string (with an implicit encoding and cost function already known) that corresponds to a program that "executes an algorithm." However, there are possibly infinitely many algorithms for which you an implement a program with. So perhaps you'll want to define the correct "fitness" metrics.

However, even for certain programs, "fitness" metrics can be somewhat hard to define. Time? Space usage? Quantification of "side effects?" Optimally, you'll generate "the shortest program" that does *only* what you want it to do.

I suppose that if you find the correct fitness metrics and adjustment algorithms, you'll be able to do this.


---

### Answer by username_9 on 2017-12-11. Score: 0

This is not a full answer and I am not very experienced in neural nets, but perhaps helpful.

NNs essentially are given an input and produce a response. They are then trained via practice to produce similar responses on "similar" inputs in the domain, for example, the same label to images of the same animal, or high ratings to "good" chess positions where good means high winning chances.

So as I commented, neural nets are a non-uniform model of computation that work in a totally different way than step-by-step algorithms run on Turing Machines. Instead, think of them as "soft" circuits that use continuous math rather than Boolean and can be tweaked or trained, and are allowed to err.

> Why is playing chess easier than Dijkstra or Graphisomorphism?

Partially, it is the difference between asking someone to answer a question to the best of their ability, and asking them for the one correct answer along with a proof that it is correct. Partially, it is the difference between solving a fixed-size problem, and simultaneously solving the problem for all possible input sizes.

Each time Dijkstra's is run on an instance, which may be of any size, it implicitly *proves* that its output is the one true answer and no other. In chess and image recognition, one gives the best answer one can and errors are tolerated. Furthermore, one only trains networks to solve these problems of one size at a time. I don't think we know yet how to generalize such a neural net solution to, say, problem instances of entirely different sizes and shapes.

I don't think we should assume that neural nets *can't* solve shortest-paths or similar algorithmic problems, but they solve problems in a fundamentally different way than a step-by-step algorithm that is always correct.

Going back to the similarity between neural nets and circuits, note that circuits have been studied for decades, yet judging by [the lack of answers to (5) of my previous question](https://cstheory.stackexchange.com/questions/23796/do-we-have-any-nontrivial-uniform-circuits), we know almost nothing about how to construct fully correct circuits for a given problem except via transforming a uniform algorithm (Turing Machine) into a circuit.

> **Comments:**
> **username_0**: I don't think having one answer makes a difference - two players can play Dijkstra by competing who can find a shorter path. Scalability might be a more serious issue - do you think NNs can learn how to play NIM?  
> **username_9**: @domotorp, I think there is a huge conceptual and practical difference between correct algorithms and incorrect but approximate heuristics. You didn't ask why chess is harder than approximate shortest paths, you asked why chess is harder than Dijkstra which is provably correct 100% of the time on all input sizes. Re: nim, no idea; you need a NN architecture that accepts arbitrarily large input to start with...  

---

### Answer by username_7 on 2017-12-10. Score: -3

"neural networks " transform a vector from one dimensional space to another dimensional space. so they are nothing more than highly , highly non-linear function approximators. even neural networks use approximation algorithms for their loss minimization . however training neural networks for devising new algorithms is out of question. tomas mikolov did some work in this area with stack augmented recurrent neural network , and i have also heard about "neural turing machines" for this domain. however finding optimal strategies has been the fundamental cause of studying reinforcement learning which is somewhat related to your question. but using neural networks for devising new algorithms is not possible , atleast in the near future.

> **Comments:**
> **username_0**: I think an optimal strategy for a suitable game is the same as an optimal algorithm for the corresponding problem.  
> **username_7**: @domotorp "strategy" is more of a heuristic than an algorithm  

---

### Answer by username_8 on 2017-12-10. Score: -4

I am a QA Automation engineer so don't claim expertise at neural networks, but, tautologically, yes NN can themselves create algorithms. Humans themselves are NN at some level, and we create algorithms, so it stands to reason that artificial NN systems we create can themselves create algorithms.


---

