On 9/12/14, Warren D Smith <warren.wds@gmail.com> wrote:
In a V-vertex E-edge graph...
What string-machine salesman Lunnon forgot to say, is that enormous edge-length integers, N bits long, would require an exponentially large budget to purchase the string, plus the thing would gravitationally collapse into a black hole.
If the edge lengths were selected from a BOUNDED set of integers only, though, then Lunnon's "string machine" for all shortest paths would work... it takes O(E+V) steps to build it, then to solve the A-B shortest path problem requires effort (force, energy expenditure versus friction, also time if you have bounded power source) of order O(E+V) to pull on that much weight.
Meanwhile the conventional computer has a linear time algorithm O(V+E) for single source, all destinations, shortest paths (assuming bounded nonnegative integer edge lengths), then constant time lookups... so, sorry, Lunnon+string has not really beat conventional computers.
SWASC is not restricted to a single "source" (starting town)! WFL
A nicer try was made by Ken Steiglitz who once invented a machine made of rigid parts to solve NP-complete problems instantly. (Some part can move, or not, if the SAT problem has solution, or not.) Really, though, it won't work, albeit the physical reasons for the failure are a bit subtle and were not understood by KS himself.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 9/12/14, Jeff Caldwell <jeffrey.d.caldwell@gmail.com> wrote:
Thank you, Hans. I enjoyed rereading the article.
On Thu, Sep 11, 2014 at 11:33 PM, Hans Havermann <gladhobo@teksavvy.com> wrote:
Jeff Caldwell: "The full article isn't as easily found online as it was years ago. 'An ancient rope-and-pulley computer is unearthed in the jungle of Apraphul By A. K. Dewdney' (v 258 no. 4, April, 1988)"
It appears in Dewdney's 1990 'The Magic Machine' compilation. I've put a scan of it here:
http://chesswanks.com/txt/TAW/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun