Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!think!nike!ucbcad!ucbvax!cartan!brahms!desj
From: desj@brahms (David desJardins)
Newsgroups: sci.math
Subject: Re: Analog models of computation
Message-ID: <27@cartan.Berkeley.EDU>
Date: Fri, 17-Oct-86 17:24:58 EDT
Article-I.D.: cartan.27
Posted: Fri Oct 17 17:24:58 1986
Date-Received: Tue, 21-Oct-86 04:11:45 EDT
References: <8194@watrose.UUCP> <6490@think.COM> <3504@columbia.UUCP> <23@cartan.Berkeley.EDU> <3516@columbia.UUCP>
Sender: daemon@cartan.Berkeley.EDU
Reply-To: desj@brahms (David desJardins)
Distribution: net
Organization: Math Dept. UC Berkeley
Lines: 29

In article <3516@columbia.UUCP> zdenek@heathcliff.columbia.edu.UUCP (Zdenek Radouch) writes:
>Now, I am not saying that the method is general, let alone practical.
>It's just DAMN simple!

   Oh, I agree it is pretty.  But it is not an argument for the value of
analog computation, since it is not practical.

>>   Again, *nonsense*.  It takes at least one time unit per edge to adjust
>>the length of the string to the specified value.
>
>Sorry, you are wrong. To solve the problem you just lift the model!

   Sorry, you are doubly wrong.

   1) From this point of view (solving a *particular* graph) a digital
computer can also do it in constant time.  Determine the answer for that
particular graph, and then write a program to print it out.
   Complexity theory only makes sense when applied to a *class* of problems,
parameterized by some parameter (in this case, the "size" of the graph,
measured in one of the several possible ways).  And, the time that it will
take you to solve a problem in this class is omega(n), unless you have an
infinitely large house full of string models of all possible graphs.  Without
such a collection, constructing the model is an inextricable part of the
solution.

   2) It takes linear time for the model to fall into place and indicate the
solution after you lift it.

   -- David desJardins