Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!think!bradley
From: bradley@think.COM (Bradley Kuszmaul)
Newsgroups: sci.math,sci.physics
Subject: Re: Analog models of computation
Message-ID: <6490@think.COM>
Date: Wed, 15-Oct-86 11:37:11 EDT
Article-I.D.: think.6490
Posted: Wed Oct 15 11:37:11 1986
Date-Received: Wed, 15-Oct-86 20:34:20 EDT
References: <8194@watrose.UUCP>
Reply-To: bradley@godot.think.com.UUCP (Bradley Kuszmaul)
Distribution: net
Organization: Thinking Machines, Cambridge, MA
Lines: 102
Xref: mnetor sci.math:2 sci.physics:2

In article <8194@watrose.UUCP> rpjday@watrose.UUCP (rpjday) writes:
>
>  I am interested in collecting examples of problems in the area of
>computation that are generally acknowledged to be reasonably to
>obscenely difficult using the digital computer model, but which have
>simple elegant solutions if one was allowed to construct some form
>of "analog" computer.  
>  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.
> ...
>R Day

Summary of the rather long article which follows:
  (1) Finding the distance betwen two points in a graph can be solved
      efficiently on a digital computer.
  (2) The analog computer you propose must grow as fast as the
      problem (the crane to lift the string must grow).  If I am
      allowed to build a digital computer which also grows then I can keep
      up with your analog computer by exploiting parallelism (e.g.
      using a Connection Machine (tm) computer system.)
  (3) The analog computer you propose does not even work.

Point (1):

I don't beleive that your example satisfies the requirements.  Finding
the shortest path between two points using a digital computer is
nowhere near obscenely difficult.  In fact it can be done in time
which is only logarithmically worse than linear in the size of the
graph by the following algorithm:

  To find the shortest distance (and in fact find a shortest path)
  from point A to point B in a (we'll even make it directed) graph
  G=(V,E) [vertices and edges]:
   Set each vertex's value to INFINITY
   Set set vertex A's value to 0.
   Let P be a priority queue, initialize P to contain A only.
   loop until P is empty
     Let V:= the smallest vertex in P (removing it from P)
     if V=A we are done.
     mark V as "VISITED"
     For each edge E from vertex V to vertex U,
       set U's value to MIN(U's old value, V's value + cost-of-edge(E))
       if U is not "VISITED" and U's value just changed,
         then change U's position in the prioty queue to reflect its new value.
     end for
   end loop
   if we get here without V ever equalling A, then "you can't get there
     from here"

Analysis: Clearly we are only going to examine any given vertex at
most once (since we examine a vertex when it is the closest unexamined
vertex, and examining a vertex which was further away is not going to
make the closer vertex any closer than it already was).  We also look
at any given edge at most once, and we recompute U's position in the
priority queue at most once per edge.  Thus the only possible way for
this algorithm to run in more than linear time is if munging around in
the priority queue takes more than constant time.  Well, the best
priority queue algorithms I know take log time for each operation,
giving us (N log N) time behavior for this algorithm.

Point (2)  The analog computer's "engine" grows with the size of the
problem.  If the digital computer is allowed corresponding growth,
then parallelism can keep up:

If we compare this to the problem of building a graph out of string
and measuring it, we need to understand how fast building the graph
really is.  If we assume that graph has been built (which seems fair,
since assume that the input to the algorithm above is ready to go),
then it looks like the string algorithm takes time which is linear in
the diameter of the graph (or some such nonesense).  At any rate, it
looks like the string has gained a linear speedup.  However, this is
not really fair, since there are some assumptions about how to
implement this algorithm that have been ignored:  For example, it
takes a rather large hoist to implement the algorithm for billion
vertex graphs, and we can conclude that the analog computer must grow
as fast as the input grows.

  For the digital computer, the corresponding growth is in the memory
components, but if your are going to charge me for the memory in my
digital computer, I will respond by replacing every memory chip with a
microprocessor chip, so that I can exploit parallelism too.  (Then we
get into an analysis of the performance of parallel algorithms to do
the same thing, and what kind of interconnection network we are
assuming between the processors...)

Point (3)  Another problem with the analog approach to solving this problem is
that it does not work.  Consider a family of graphs with bisection
width which is linear in the number of vertices (e.g. in a binary
hypercube containing N vertices, we have to cut N/2 edges in order to
bisect the graph).  Such a graph, when built out of string, and hung
from a crane, starts getting fat around the center.  The fact that the
string has finite thickness is going to get us.  Some of the strings
will not hang straight down from point A to point B, but will have to
take a slight horizonta  detour to get around the other strings which
are trying to get from point A to point B.


 - bradley@think.com or think!bradley