[math-fun] string salesman Lunnon
Your machine asymptotically does NOT exhibit constant time "lookup" to solve an A-B shortest path problem, that is where you are confused. The mass you are pulling on and the friction both grow with N... So anyhow as I tried to demonstrate this machine really is worse than conventional algorithms...
One has to be extremely generous when talking about complexity of the analog computers. Any argument with "friction" in it implies (as far as I see) that analog computer do not work (complexity wise) at all. It's like saying that IEEE number are not reals and so you cannot do any computation with reals on a computer (very true and at the same time total rubbish). One IMO more valid critique Fred's method would be "how do you pick the two cities in O(1)"? But then I rather marvel at those thingies and enjoy... Best, jj * Warren D Smith <warren.wds@gmail.com> [Sep 14. 2014 15:02]:
Your machine asymptotically does NOT exhibit constant time "lookup" to solve an A-B shortest path problem, that is where you are confused. The mass you are pulling on and the friction both grow with N...
So anyhow as I tried to demonstrate this machine really is worse than conventional algorithms...
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
One IMO more valid critique Fred's method would be "how do you pick the two cities in O(1)"?
Good point: realistically(!), that's always going to cost time at least O(log V) . Ssh --- don't tell my class ... WFL On 9/14/14, Joerg Arndt <arndt@jjj.de> wrote:
One has to be extremely generous when talking about complexity of the analog computers.
Any argument with "friction" in it implies (as far as I see) that analog computer do not work (complexity wise) at all. It's like saying that IEEE number are not reals and so you cannot do any computation with reals on a computer (very true and at the same time total rubbish).
One IMO more valid critique Fred's method would be "how do you pick the two cities in O(1)"?
But then I rather marvel at those thingies and enjoy...
Best, jj
* Warren D Smith <warren.wds@gmail.com> [Sep 14. 2014 15:02]:
Your machine asymptotically does NOT exhibit constant time "lookup" to solve an A-B shortest path problem, that is where you are confused. The mass you are pulling on and the friction both grow with N...
So anyhow as I tried to demonstrate this machine really is worse than conventional algorithms...
_______________________________________________ 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
Not just analog computers. I recall one wag wrote about the incredible mass of the takeup reels on a Turing Machine tape transport. Perhaps someone else can recall the reference. At 06:40 AM 9/14/2014, Joerg Arndt wrote:
One has to be extremely generous when talking about complexity of the analog computers.
participants (4)
-
Fred Lunnon -
Henry Baker -
Joerg Arndt -
Warren D Smith