Hacker News Reader

Comment by r34 | Hacker News Reader

As a complete amateur I was wondering if it could be possible to use that property of light ("to always choose the most optimal route") to solve the traveling salesman problem (and the whole class of those problems as a consequence). Maybe not with an algorithmic approach, but rather some smart implementation of the machine itself.

View on HN

If somehow you can ensure that light can only reach a point by travelling through all other points then yes.

It's basically the same way you could use light to solve a maze, just flood the exit with light and walk in the direction which is brightest. Works better for mirror mazes.

Google up 'soap film steiner tree' for a fun, well-known variant of this.

Then follow it up with https://www.scottaaronson.com/papers/npcomplete.pdf . While reality can "solve" these problems to some extent it turns out that people overestimate reality's ability to solve it optimally.

Sounds like some of the trendy analogy computing approaches, like this one for example:

https://www.microsoft.com/en-us/research/uploads/prod/2023/0...

This is pretty likely, it's been done with DNA: https://pubmed.ncbi.nlm.nih.gov/15555757/

Physics contains a lot of 'machinery' for solving for low energy states.

This sounds a bit like LIDAR implementations, I assume you mean something similar at a smaller scale, where physical obstacles provide a "path" representation of a problem space?

Yup, something like that came to my mind first: create a physical representation (like a map) of the graph you want to solve and use physics to determine the shortest path. Once you have it you could easily compute the winning path's length etc.

Reply on news.ycombinator.com