Xref: utzoo comp.software-eng:2577 comp.theory:95 Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!rex!ukma!uflorida!mephisto!mcnc!duke!grad19!srt From: srt@grad19.cs.duke.edu (Stephen R. Tate) Newsgroups: comp.software-eng,comp.theory Subject: Re: computational complexity (was: CS education) Message-ID: <16296@duke.cs.duke.edu> Date: 1 Dec 89 19:55:57 GMT References: <2608@fai.UUCP> <34818@regenmeister.uucp> <10014@june.cs.washington.edu> Sender: news@duke.cs.duke.edu Distribution: usa Lines: 100 The following quoted posting went on and on and on and on and on..... I tried to cut out most of the excess garbage, but without much success. In article <10014@june.cs.washington.edu>, peterd@cs.washington.edu (Peter C. Damron) writes: > > >> Computability is the study of what can be computed. > >> Complexity theory is the study of how hard things are to compute. > > >What's the difference? If Joe Shmoe thinks computable means P, then by > >your definition, computability is the study of what's in P. If Sally > >Shmoe thinks computable means NP, then by your definition, computability > >is the study of what's in NP. If John Shmoe thinks computable means > >Post-Turing computable, then by your definition, computability is the > >study of what Post-Turing machines can do. > > Here you are confusing "computability theory" with computational > complexity theory. I don't think the term "computability theory" is used > any more (if it ever was). I have never heard the term "computability theory" used either. Of course, people do talk about what functions are computable, and the common term for this study is "recursion theory" -- not computability theory. (I believe that Church's thesis is pretty well accepted for the definition of "computable".) Furthermore, using the term "computability theory" to refer to anything with complexity classes seems to be very much against common sense. Complexity classes such as P and NP are all measures of how hard things are to compute -- meaning that they are indeed computable! It just might take a long time to do so. > >> People studing complexity theory often develop new algorithms to solve > >> problems, but that is a side issue to showing the complexity class of > >> the problem. > > >Oh, give me a break. I recently proved that if n-digit multiplication > >and addition take time O(M(n)) where n^a = O(M(n)) for some a > 1, then > >n digits of e can be computed in time O(M(n)). (The best previous result > >is O(M(n) log n), which also applies for a = 1, if you care.) I had to > >develop a new algorithm to achieve this result; do you really think I > >consider the algorithm a ``side issue''? Harrrumph. Side issue: how can you assume n^a = O(M(n))??? Are you assuming that a can be vanishing (smaller than a constant)? If not, then simply looking at Shonhage-Strassen multiplication shows that n^a is NOT O(M(n)) for any constant a>1. Furthermore, if you are considering a less-than-optimal multiplication algorithm, then is shaving off a log(n) all that important? The result WITH the log(n) and using the S-S multiplication algorithm gives better results. This is really just a side note to whoever wrote the above paragraph -- E-mail me about this please (I have lost track of who is who in the long posting). > The algorithm is part of the proof. > It might be possible to prove the same thing without > the algorithm or with a different algorithm. > This does not mean that the algorithm is not useful. Chill out people -- you're taking this far too personally. Whether the algorithm is simply a method to the proof or whether it is the main point of interest is a matter of context. IN GENERAL, a complexity theorist is not very interested in making new algorithms that shave a log(n) off of the complexity of an algorithm -- because that will not put the problem in a significantly different complexity class. (I'm talking about the above example, actually -- it can make a big difference in talking about complexity classes that are defined by such slowly growing functions, such as NC, AC, L, etc.) I don't think it's too extreme to say that if the algorithm is the main point of interest then the work can be considered to be in the "theory of algorithms" (or "algorithmics" as some people call it), and if complexity classes are the main point of interest then the work can be called complexity theory. > >> >(I'm in math, not computer science. Computability theory is definitely > >> >CS; numerical analysis is definitely math; computational complexity > >> >theory is somewhere in between.) > >> > >> Wrong. Complexity theory is definitely computer science. > > I would maintain that both computational complexity theory and applied > computational complexity are parts of computer science. This > is because both are based on an underlying model of a computing machine > (usually a Turing machine). The work in both of these areas cannot > be expressed without this model (as far as I know). > > >> Also, there are two kinds of numerical analysis, the kind done by > >> mathemeticians and the kind done by computer scientists (or engineers). > >> Mathemeticians deal with abstract numbers like integers and reals. > >> Computer scientists deal with limited precision numbers. Why do people insist on classifying things into departments???? I've seen recursion theory done by mathematicians and computer scientists. I've seen complexity theory done by both -- logic done by both. And the final statement is completely ludicrous -- I consider myself a computer scientist (because I'm in a computer science department, if for no other reason), and I do NOT deal with limited precision numbers. I deal with abstract notions (numbers????) that include the integers and reals (actually rings and fields). And there are plenty of mathematicians that I've seen who worry about limited precision of computers. Now -- can we please be finished with this silly categorizing and move on to something interesting? Steve Tate ARPA: srt@duke.cs.duke.edu UUCP: ..!decvax!duke!srt Brought to you by Super Global Mega Corp .com