are you only interested in efficient solvability of classic problems?

Yes. For examples, I have devised algorithms in the past.

"On one hand, we know that the computational power of neural networks is TC0." I think that's only if you have a very limited depth as in the question you link. As Yaroslav Bulatov says in a comment there, "One hidden layer networks are known to be universal approximators in a sense that any continuous function can be approximated arbitrarily close."

Neural nets are nonuniform models of computation, i.e. each one has a fixed size. Whereas we tend to consider an algorithm to be a uniform model of computation that can solve instances of the problem of all sizes. So I think your question will fall quite a bit outside normal paradigms of NN usage.

@usul But there are many settings in which it is sufficient to solve a finite problem, and a solution to the finite problem implies a uniform algorithm; this way one can use computers to synthesise uniform algorithms. Often this is done nowadays with e.g. SAT solvers, but maybe one could replace here Boolean formulas and SAT solvers with e.g. neural networks and backpropagation?

@Kaveh: I'm very surprised that neural networks cannot learn multiplication. I mean there's such a simple algorithm for it. Or is there any explanation why winning in board games is easier for them than learning the multiplication rule thought in elementary school?

@Andrej: And how much time would it take for you to train yourself to solve FACTORIZATION?

@domotorp: Do you mean "devise an algorithm for factorization?" That's easy: just try all possibilities, as they are only finitely many. I never said I was a very good neural net.

This seems underspecified: "For example the network would get an input graph G with weighted edges, and two vertices ss and tt specified, and we asked it to find a shortest st path as fast as possible". You don't "ask" a neural network to do something in this way. You train it on some data. What would the data be in this case? Examples of graphs with correctly labeled shortest paths? Generated from what distribution? You can only expect the network to perform well on the same distribution.

Re multiplication, I asked Ilya and he pointed me to this paper:arxiv.org/abs/1511.08228

@Sasho: I also thought that data used to be required, but apparently not anymore, as these AlphaGo Zeros train themselves from scratch by playing each other. If you insist turning it into a two-person game, there are many possible variants, like whoever finds a shorter path with some time limit wins.

@Kaveh: As not being an expert in neural networks, I cannot really understand from the linked paper why playing chess should be easier than Dijkstra. I would really appreciate any sort of answer that a complexity theorist can understand.

I am neither an expert. The ability to play games at human level is a very recent advance. They combined reinforcement learning with DNNs. Intuitively, they do a back track, they use DNNs to compute the value of each position and to compute which branches to explore. These DNNs are trained by playing a very large number of games and the result of the game is feedback through the play to update the weights of the DNNs.

@domotorp I guess one part of the answer is that playing chess might be comparable to developing a local heuristic rule for finding approximately shortest paths in some specific real-world setting. (Think of something like "you are somewhere in an unknown city and you would like to find a supermarket", and then try to program a robot to solve this based on what its camera sees.) Here the neural net could learn to evaluate the "quality" of each position reachable from the current position, and then the final algorithm would just go in the direction that the neural net thinks promising.

(continued) I think Dijkstra in the general case is something that is rather ill-suited for any kind of a local heuristic rule, and this is one of the challenges that we will have if we try to solve it with machine learning techniques.

[cont.] You can probably do something similar for finding shortest paths in graphs. But I think the real issue is what you are trying to do. Maybe look at this way: playing chess at human level is not the same as playing optimal strategy in chess. DNNs are helpful for problems that are hard to solve by direct programming like object recognition, playing chess, ... So if you want to think about it this way what you want is not just learning some particular graph algorithm but to learn to solve a large class of algorithmic problems.

[cont.] It is easy to teach someone to run Dijkstra, it is a totally different story to teach someone to invent algorithms. I know people are trying it but hasn't happen yet afaik.

@Jukka: I also guess that the situation is something like this. This, for example, quite interestingly would not exclude the possibility that one day someone finds a very simple chess algorithm that would beat the current bests! Can we point to some complexity class (like PLS) that describes problems solvable this way?

Btw, can neural networks win in NIM?

Keep in mind that generalized Go is ExpSpace-complete. Re Nim, interesting question, I think it is not difficult for say DeepMind's Atari algorithm to win against most humans who don't know the optimal winning strategy.

@Kaveh: I wonder how AlphaGo would play Go on a different board size (I mean without adjustments).

Perhaps not exactly what you were asking but still relevant: arxiv.org/pdf/1712.01208.pdf

I just found out this exists: arxiv.org/abs/1704.01665

So this shows that NNs can be trained to solve graph theoretic problems! The above paper only considers NP-hard problems, so the question remains about problems in P.

@SashoNikolov, as I understand from page 3 of that paper, it doesn't use nn to provide an algorithm for those problems. It directly solves those problems by nn. I think domotrop asked for designing algorithms by nn not solving problems by (generic) nn algorithm. So the output of the network should be an algorithm not a min vertex cover for particular instance.

@domotorp, are you looking for solving problems by nn or you want to design algorithms by nn (and those algorithms solve the problems). As I understand you want nn to generate sth like dijekstra algorithm not solving a particular instance. If this is the case, the above paper doesn't seem to help.

@Saeed I have only skimmed the paper but I do not think their NNs output a vertex cover. The NN outputs an evaluation function, used for choosing the next element to add to a solution in a greedy algorithm. The evaluation function itself is a very simple algorithm, parametrized in some way, which can be run as a part of a greedy algorithm on other instances. It's all quite constrained but that's not surprising.

@Saeed I wanted the nn to solve the problems (and from how it's done, deduce something about the algorithm they implicitly use). How could an nn design an algorithm, I mean what kind of output are we looking for?

@Sasho, yes I also think the nn outputs some evaluation function. I say nn doesn't generate an algorithm itself.

@domotorp, maybe I missinterpreted your discussions in comments. I guess this was that comment: "I wonder how AlphaGo would play Go on a different board size ...." that said, my feeling was that you want it to provide a self adjusting algorithm (infinite many inputs). So I thought for the case of shortest path you want ask nn to give an algorithm that solves any input instance. E.g. the nn suggested in the above link, as my understanding is biased by a data set, but the chess example that you discussed is not biased by any dataset (I guess similarly goes for go).

Or maybe it was this comment (all of them have same spirits): "why playing chess should be easier than Dijkstra.". I said either you missed the point that for chess we have one very simple input but for shortest paths we have infinitely many possible inputs, or you know this but you are looking for an algorithm not solving just a specific instance

Re different size boards, I think it would do quite well, it is really understanding the game and positions. You might find this talk helpful: youtube.com/watch?v=Bm7zah_LrmE

@Saeed We can restrict Dijkstra for graphs on at most 1000 vertices, I guess. Another option would be to allow any input size for an NN and require it to output a solution, but I don't know how much harder this would be. Judging from Kaveh's last comment, probably not much.

@domotorp, if we apply the restriction the problem could be easier, e.g. I remember a colleague of mine did his bachelor thesis on shortest paths in grid graphs by nn and genetic algorithms (it was for robotic purposes). He got reasonable results while he didn't train the network by all possible grid graphs. The main issue is that those algorithms are not optimal. So expecting an excellent algorithm like Dijkstra really is something hard.

For chess, despite the fact all possible positions are theoretically restricted, we cannot reach that theory restriction in practice. So the engines (like stockfish) are just a benchmark, they are not perfect (unlike the Dijkstra). I didn't watch Kaveh's video but I guess it is again a comparison with non-perfect algorithms/machines etc. P.S: Maybe the problem is that I took those words very series and interpret them literally into a perfect algorithm. If we want a reasonable algorithm nn might be fine, for perfection I doubt, at least I think they aren't perfect right now, even for chess.

@Saeed For chess surely they aren't perfect, but there we don't expect a simple solution. For STCONN, we know that there is a simple algorithm, and to be honest, I think that anything that's only near-optimal got to be more complicated. So I see no reason why Dijkstra couldn't be discovered by NNs.

@domotorp, let fix one thing, you really want nn to discover dijekstra (or so), not just solving the shortest path, am I right? If this is the case, as I said earlier, it seems it is hard to train it. Maybe we get sth very close to optimal but not the optimal. I don't know what would be the input to the network. I almost don't know anything about nn, but I don't know what could be the formulation of the input (if we do not concentrate on datasets).

So this is only slightly related, but I suspect neural networks could find NP-Completeness reductions automatically in similar ways that they do with other algorithms. The nice thing about automatic reductions is if you reduce a problem to a different problem that has a nice algorithm then you get a good algorithm for yours as well (assuming the reduction is fairly efficient)