Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!cs.utexas.edu!rice!uw-beaver!uw-june!peterd
From: peterd@cs.washington.edu (Peter C. Damron)
Newsgroups: comp.software-eng
Subject: Re: CS education [engineering, mathematics, and computer science]
Message-ID: <9963@june.cs.washington.edu>
Date: 28 Nov 89 19:52:47 GMT
References: <2608@fai.UUCP> <34818@regenmeister.uucp> <9924@june.cs.washington.edu> <4059@sbcs.sunysb.edu>
Reply-To: peterd@june.cs.washington.edu (Peter C. Damron)
Distribution: usa
Organization: University of Washington, Computer Science, Seattle
Lines: 64

Sorry for posting this stuff to this group, but I hate to see misconceptions
go unnoticed.

Obviously, Dan Bernstein did not read what I wrote or did not understand it.

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.
Computability is the study of what can be computed.  There are
intractible problems that cannot be computed (e.g. the Post correspondence
problem).  Complexity theory is the study of how hard things are to
compute.  Complexity theory divides problems into classes like P and NP
and studies the relationships between the problem classes.

>Practical complexity theory (what ``computational complexity theory''
>used to mean) studies fast algorithms for practical problems.

Wrong.  There is complexity theory, and there are applications of complexity
theory.  Your "practical complexity theory" is simply applications.
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.

>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'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.

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.

Perhaps mathemeticians don't understand computer science.

I'm not a computer science theory person, but at least I know what the
theory is all about.

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