Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!rutgers!nike!ucbcad!ucbvax!ernie.Berkeley.EDU!tedrick
From: tedrick@ernie.Berkeley.EDU (Tom Tedrick)
Newsgroups: sci.math
Subject: Re: Analog models of computation
Message-ID: <16145@ucbvax.BERKELEY.EDU>
Date: Wed, 15-Oct-86 23:52:43 EDT
Article-I.D.: ucbvax.16145
Posted: Wed Oct 15 23:52:43 1986
Date-Received: Thu, 16-Oct-86 02:23:53 EDT
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: tedrick@ernie.Berkeley.EDU.UUCP (Tom Tedrick)
Distribution: net
Organization: University of California, Berkeley
Lines: 20
Summary: linear time is slow?

>>>  As an example, the problem of finding the shortest path between two
>>>points in a graph is easily solved if one is allowed to build a string
>>>model of the graph, then pick it up by the source node, and measure the
>>>distance straight down to the target node.  I'm sure everyone is familiar
>>>with this trick, but I'm also sure there were other "analog" models
>>>of computation, some for supposedly intractable problems.

>>I don't believe that your example satisfies the requirements.  Finding
>>the shortest path between two points using a digital computer is
>>nowhere near obscenely difficult....

The problem of finding a "shortest path" in a graph is a bad example
to use because it can be solved very quickly (linear time if I remember
correctly. Bondy & Murty give a simple quadratic time algorithm.).

What would be interesting are examples of fast analog algorithms for
NP-hard problems.

I liked the string analogy though. Let's hear some more of these
intuitive algorithms ...