6 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

• ljlolel 3y ago
  Seems 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 3y ago
    A (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 3y ago
  No, 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 3y ago
    Or.. 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 3y ago
  How does this solve traveling salesman exactly?
  • anshumankmr 3y ago
    What the electrons are doing seems closer to Djikstra than TSP
    • thehappypm 3y ago
      Agree
• khazhoux 3y 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 3y ago
  Analog 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).