Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!caip!think!bradley From: bradley@think.COM (Bradley Kuszmaul) Newsgroups: sci.math Subject: Re: Analog models of computation Message-ID: <6528@think.COM> Date: Mon, 20-Oct-86 12:46:10 EDT Article-I.D.: think.6528 Posted: Mon Oct 20 12:46:10 1986 Date-Received: Tue, 21-Oct-86 23:31:24 EDT References: <8194@watrose.UUCP> <6490@think.COM> <3504@columbia.UUCP> Reply-To: bradley@godot.think.com.UUCP (Bradley Kuszmaul) Distribution: net Organization: Thinking Machines, Cambridge, MA Lines: 158 In article <3529@columbia.UUCP> zdenek@heathcliff.columbia.edu.UUCP (Zdenek Radouch) writes: >In article <27@cartan.Berkeley.EDU> desj@brahms (David desJardins) writes: >>In article <3516@columbia.UUCP> zdenek@heathcliff.columbia.edu.UUCP (Zdenek Radouch) writes: >>> >>>Sorry, you are wrong. To solve the problem you just lift the model! >> >> Sorry, you are doubly wrong. > >You are very confused about what it takes to find the shortest path between >two vertices in a graph. [...] I hate it when people say "You are very confused". Is it not enough to be merely confused? Besides, I don't think he is confused. > In order to implement the function you have to use >primitive operation COMPARE. > >It turns out, that relational operators in mathematics are always applied >to TWO operands, hence your additional time if n>2. One model of computation is that you have to use the primitive operation COMPARE, but there are certainly other models. For example, I I had a model of computation which gave me MIN of an arbitrary set as a primitive operation, I might be able to implement this algorithm in truly constant time. However, I don't have an implementation for such a model, so I don't spend too much time thinking about it. On the other hand, I don't have an implementation for a model in which a binary comparision takes unit time either. Typically, as the size of the problem grows, the size of the numbers grow also, and the time it takes to do a comparision of two K bit numbers is at least (log K). >His model together with his eyes happen to perform FULL PARALLEL compare, >therefore time = 1. > >As I said, his method might not be practical, but it's elegant and > much faster. If it is not practical, then how can it be faster. I am never happy with very fast algorithms that produce the wrong answer when I program them myself. I don't see why I should be more forgiving of a program which someone else builds out of string. > >> 2) It takes linear time for the model to fall into place and indicate the >>solution after you lift it. >Only when you consider Grurmstipth's force acting on the beads. It's been >known for years, at least in physics, that the time, n falling beads take to >fall, is INDEPENDENT of n. I am not sure why you are introducing Grurmstipth at this point. Did you intend the above paragraph to be a :-)? If so, pardon me for being serious... It is going to take at least linear time (linear in the answer rather than linear in the input) for the model to fall into place, since some bead must fall at least the distance from the crane (hoist, hand... etc) to where it lands and is measured. Even if the silly bead had already fallen to its position, you could argue that it will take linear time just to measure it (e.g. by bouncing a laser of the bead in question, and measuring the time it takes for the laser beam to return). Incidently, several people have complained that some of my other criticisms of this algorithm were wrong. For example, as far as innaccuracy goes, let me state that I was allowing the string to be arbitrarily precise, but that I did assume that the string has some finite width. In that case, as the graph gets very large, the width of the hanging string (as a collection of strings) becomes important. It is conceivable that the shortest string would not be allowed to fall straight down, but that it would have to go around the lump in the center of the bundle of strings, and that therefore some other string might "think" it was the shortest string, giving a wrong answer. If you assume the string as zero width, then I can't argue much more than that at least I know how to build a digital computer, but not a zero width string. ________________ Some people have objected to the fact that I use more memory in a digital computer as the size of the problem grows, and that I replaced the memory chips with processor chips at some point in my argument. I think that my position here needs to be clarified. As a string advocate, you can take one of four positions, characterized by the cross product of two binary choices: (1) The string model is charged for the amount of string it uses up. (2) The string model is not charged for the string it uses. and indendently (A) The digital computer is charged for the memory it uses, or (B) The digital computer is not charged for its memory. Now as an advocate of the string model, I don't suppose you will support the combination of choices (B) and (1), since then the digital computer comes out cheaper. If you choose (2) and (B) then both machines can solve an arbitrary problem for unit hardware. The digital computer takes around linear time in the inputs, and string computer takes an amount of time which we can't seem to agree upon. (Linear in something or the other?) If you choose (1) and (A) then both machines have a hardware cost which is proportional to the size of the input problem. If you choose (2) and (A) then you are being unfair, but since you are charging me hardware costs which are linear in the size of the problem I might as well use the hardware of my choice rather than the hardware of your choice, and replace the memory chips with processor chips. This has the same cost (it is linear in the input) but now I can at least exploit parallelism and do about as well as your parallel machine. In fact, I could have taken this tact if you had chosen (1) an (A) too. I think the string and the memory are very similar. Either you charge for both or you charge for neither. I think it is more realistic to charge for both... ________________ Some people have argued that the advantage of the string algorithm is that it is easier to understand. My algorithm took "eighteen lines of code" and some more explanation. (BTW The explanation should not be counted as part of the algorithm. The explanation was analysis of the algorithm's performance, which noone has argued about. No analysis of the string machine's performance can make the same claim about being accepted by everyone). (Even the algorithm itself only took eighteen lines to describe because I was being overly verbose. The corresponding parallel algorith, when written in Connection Machine Lisp (see various sundry and published and unpublished papers by Guy Steele and Danny Hillis, mumble mumble cite cite mumble mumble) is only four lines long, and that description included parallelism. More fundamentally, I have never considered "the complexity of algorithms" to include the complexity of "how hard it is to understand the algorithm". An algorithm only has to be written and analyzed once, and that portion of the "complexity" is constant, independant of the size of the input. ________________ I also have the belief, with no proof, that there are no analog machines which will do better than digital machines, because whatever analog machine you build, I can build a digital machine with about the same hardware cost, and the digital machine will be able to simulate the analog machines behavior with only a small decrease in performance (e.g. typically a polylogarithmic decrease in performance). If you accept that handwaving argument, then it would be very unlikely that there is an analog computer using only a polynomial amount of hardware which can solve an NP-hard problem in polynomial time. >> -- David desJardins >zdenek -Bradley (think!bradley or bradley@think.com)