4 ms·
Can you solve arbitrary traveling salesman problem with that? There is only a polynomial number of required laser cuts (n nodes, n * (n-1) edges) and the source
by bitL 4y ago
Can you solve arbitrary traveling salesman problem with that? There is only a polynomial number of required laser cuts (n nodes, n * (n-1) edges) and the source can be next to sink with a fake 0 edge between them.
- ljlolel 4y agoSeems doable. Or better do a problem that is NP-Complete or in a highly parallelizable class. Essentially an analog computer. Some of the reason people want quantum or DNA computers to exploit physical mechanisms beyond stacks of binary gates.
- pishpash 4y agoA (classical) analog computer is not a quantum computer and various conjectures on complexity say that they should all be efficiently (polynomial-time) simulated by a probabilistic Turing machine.
- teraflop 4y agoNo, it would give you the approximate shortest (least resistance) path between the source and sink, which is very different from the traveling salesman problem (which requires finding the shortest path that touches every node). I say "approximate" because, as has been discussed in this thread, the current actually follows every possible path to some extent, weighted by their resistance. So when there multiple branching paths with similar costs, they will have similar current flow, and the current along each path is not constant. So in general it can be difficult to find the exact minimum resistance path just by measuring the current.
- px43 4y agoOr.. use non-conductive coated wire to wire up every possible path, with all the wires connected at a start and finish point, and then see which wire gets hot first. It's not going to save you any time, since wiring up every path is basically the same as brute forcing every path anyway, but it would work.
- thehappypm 4y agoHow does this solve traveling salesman exactly?
- anshumankmr 4y agoWhat the electrons are doing seems closer to Djikstra than TSP
- thehappypm 4y agoAgree
- khazhoux 4y ago> Can you solve arbitrary traveling salesman problem with that? Yes, you can solve TSP in linear time using electricity. First step is to construct a circuit with a single source, and multiple independent paths -- one for each possible TSP graph traversal. Constructing this circuit can take a bit of time, but after that, finding the shortest path will be extremely fast.
- tsimionescu 4y agoAnalog computers set up right can solve very small instances of NP problems extremely fast. However, they do not scale, as the measurement step (which is required to actually obtain the solution) becomes harder and harder with the size of the problem, as you need to distinguish finer and finer details. The energy needed to distinguish between two possible output values becomes prohibitive quite quickly (it may actually be exponential in the size of the problem, I'm not sure).