3 ms·
Here is a problem that I've been thinking about for some time: suppose I express using some type of logic that I want the shortest path between two vertices of
by linguae 7y ago
Here is a problem that I've been thinking about for some time: suppose I express using some type of logic that I want the shortest path between two vertices of a graph. Given this logical description of the problem, is it possible for a computer program to emit Dijkstra's algorithm or some other efficient algorithm? One of the things that have interested me lately is logic programming, but I'm wondering if there has been any research done on using logic programming as a means of algorithmic discovery? What are the theoretical limitations of doing this? It took bright minds to come up with the various graph algorithms that we use today, and so I'm assuming there's a fundamental limitation that makes it difficult to convert declarative expressions of a problem into specific efficient algorithms.
- kawzeg 7y agoI remember minikanren being able to generate expressions that evaluate to a value. In general, I guess the search space of all algorithms that might or might not solve a problem is simply extremely huge, so you'd need some good heuristics to find an interesting algorithm. I can't think of any reason why there would be a theoretical limit on this, but I'm no expert in this.
- tr352 7y agoPerhaps what you’re thinking of is inductive logic programming, although I’m not sure that field has advanced to the point where your particular example can be solved.