peterd@cs.washington.edu (Peter C. Damron) (12/01/89)
Sorry to continue this pointless discussion on this newsgroup. There seems to be some confusion in terminology. In article <4092@sbcs.sunysb.edu> brnstnd@stealth.acf.nyu.edu (Dan Bernstein) writes: >In article <9963@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: >> In article <4059@sbcs.sunysb.edu> brnstnd@stealth.acf.nyu.edu (Dan Bernstein) writes: >> >In article <9924@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: >> >> Computability and complexity theory is unrelated to numerical analysis. >> >There are two sides to complexity theory. Theoretical complexity theory >> >(better called computability theory) studies issues like P = NP. >> Wrong. Complexity and computability are two different things. >There was once a useful semantic distinction between computability >theory and (computational) complexity theory. I was pointing out that >when people say ``theoretical complexity theory,'' they usually mean >what ``computability'' used to mean. And you say that's wrong? I may be unfamiliar with some obsolete terminology concerning computatbility and computational complexity. I suggest that you read: "Introduction to Automata Theory, Languages, and Computation" by Hopcroft and Ullman, Addison-Wesley, 1979. It uses the terminology the way I do. I believe that this is the currently accepted norm. >> 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. John Shmoe is correct, Joe and Sally are incorrect. Some functions are not computatable, some are. Computatility is the property of being computable (regardless of how efficient that computation might be). >> Complexity theory divides problems into classes like P and NP >> and studies the relationships between the problem classes. >The fact is that computability theorists sit around talking about P >versus NP and all the other classes; the more theoretical ones think >about Church's thesis and Godel's theorem... >...Your distinction is a play upon words and does not match how people think. 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). >> 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. 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. >The travelling salesman is computability theory. e is computational >complexity theory (``applied complexity theory'' if you like). In modern terminology, the "travelling salesman" is a problem, "e" is a real number. >> >Particular problems in practical complexity theory (e.g., computing pi >> >to many digits; or computing the sine of a floating-point number) have >> >quite a lot to do with numerical analysis. >> >> Wrong. Computing digits of Pi or computing the sine function have nothing >> to do with complexity thoery (though these problems may be classified >> into a complexity class). How to do the computation of Pi or sine is >> numerical analysis. How difficult it is to compute those things is an >> application of complexity theory. >I stand by my statement that those particular problems have a lot to do >with numerical analysis. Yes, but you said they were "problems in practical complexity theory". I said they are problems of numerical analysis. >Your ``how to do it'' versus ``how hard it is'' is silly. You've never heard of the difference between a constructive proof and a non-constructive proof? >Your paragraph (past ``wrong'') doesn't contradict my statement, but >instead says that those problems ``have nothing to do with complexity >theory.'' Again you're playing with words; would you agree that they are >``applied 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. >Read my lips. Computability theory (what you would call theoretical >complexity theory) is definitely computer science. Computational >complexity theory (what you would call applied complexity theory) >is floating somewhere in between. As I have done a bit of work in the >subject and keep up with the computational complexity journals, I am >confident in making these assertions. 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. >Please tell me what separates those two ``kinds.'' Can you tell the >articles apart in SIAM JNA or Math. Comp.? Can you divide the journals >into parts, saying, ``Now this has a real number in it... but this deals >with limited precision numbers... but this one has an integer in it...'' If the author or the journal has not made the distinction, then it is probably not worth reading, beacuse there is an important difference. Peter. --------------- Peter C. Damron Dept. of Computer Science, FR-35 University of Washington Seattle, WA 98195 peterd@cs.washington.edu {ucbvax,decvax,etc.}!uw-beaver!uw-june!peterd
srt@grad19.cs.duke.edu (Stephen R. Tate) (12/02/89)
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
brnstnd@stealth.acf.nyu.edu (Dan Bernstein) (12/02/89)
In article <10014@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: > There seems to be some confusion in terminology. I'm not confused... There seems to be a difference between ``old-timers'' (the type who learn computer science from Knuth's books) and progressives (the type who ignore Knuth in favor of Aho-Hopcroft-Ullman, Hopcroft-Ullman, and perhaps Graham-Patashnik-Knuth). Anyway, as long as we agree on the content of what we're talking about, it doesn't matter how we label it; so let's both shut up about terminology. > >The fact is that computability theorists sit around talking about P > >versus NP and all the other classes; the more theoretical ones think > >about Church's thesis and Godel's theorem... > >...Your distinction is a play upon words and does not match how people think. > > Here you are confusing "computability theory" with computational > complexity theory. Labels aside, I'm arguing against your distinction between computability (as in computable functions, Pi_1, etc.) and complexity (as in NP), since almost the same groups of people study both. More below. > >The travelling salesman is computability theory. e is computational > >complexity theory (``applied complexity theory'' if you like). > > In modern terminology, the "travelling salesman" is a problem, > "e" is a real number. Stop the word games. Do I need to write everything out? ``The problem of computing e to many digits.'' Sheesh. [ particular problems, like computing the sine function ] > Yes, but you said they were "problems in practical complexity theory". > I said they are problems of numerical analysis. This is a special case of our basic argument, below. > >Your ``how to do it'' versus ``how hard it is'' is silly. > > You've never heard of the difference between a constructive proof > and a non-constructive proof? Here it is, our basic argument. There's certainly a difference between those two types of proof; but the same people are going to work on the same problems, whether their proofs are constructive or not. ``You see, these people are complex analysts. They use constructive proofs. They're applied mathematicians. These other people aren't complex analysts: they're analytic function theorists. They use nonconstructive proofs. They're pure mathematicians.'' That's an impossible distinction to make; is this really why you separate computability from complexity? Certainly there are people who care about this difference; Devlin has a book on constructibility. But most people don't care. You can't put complexity people into the ``can do'' and ``how well?'' camps any more than you can put complex analysts into the same camps. > I would maintain that both computational complexity theory and applied > computational complexity are parts of computer science. Okay; this distinction, like pure math versus applied math, applied math versus physics, and so on, does not have a clear boundary. I'm willing to place Pi_1 squarely in computer science, but I still hold that the applied problems are somewhere in between. > 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). Ummm, no. Take this working definition of (applied) complexity theory: Some variables (the inputs) are given; the rest are defined in terms of others, by whatever mathematical operations I want. The definitions must be non-circular: I must be able to assign a finite integer ``time'' to each variable so that the inputs have time 0 and all the variables in a definition have a smaller time than the variable being defined. Now I specify certain other variables (the outputs). The ``how'' question: Given that the outputs must be related in a specified way to the inputs, and given a certain set of allowed operations, how may I specify intermediate variables to obtain the outputs? The ``how fast'' question: Given a particular computation or class of such, and given an assignment of cost to each operation, what's the total cost? That's about the lowest level that I would use to think about problems, and it's a far cry from a Turing machine. I don't care that much about the implementation of the operations, though I do have to make sure my operations have realistic costs. The whole thing is somewhere between math and computer science. [ numerical analysis: mathematics versus computer science ] > If the author or the journal has not made the distinction, then it is > probably not worth reading, beacuse there is an important difference. Well, what's the difference? I'd love to know; I must have been getting a lot less out of SIAM JNA and Math. Comp. than I could have! ---Dan