Xref: utzoo comp.software-eng:2561 comp.theory:88 Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!rice!uw-beaver!uw-june!peterd From: peterd@cs.washington.edu (Peter C. Damron) Newsgroups: comp.software-eng,comp.theory Subject: Re: computational complexity (was: CS education) Message-ID: <10014@june.cs.washington.edu> Date: 30 Nov 89 21:43:13 GMT References: <2608@fai.UUCP> <34818@regenmeister.uucp> <9924@june.cs.washington.edu> <4059@sbcs.sunysb.edu> <9963@june.cs.washington.edu> <4092@sbcs.sunysb.edu> Reply-To: peterd@june.cs.washington.edu (Peter C. Damron) Distribution: usa Organization: University of Washington, Computer Science, Seattle Lines: 145 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 Brought to you by Super Global Mega Corp .com