Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!gem.mps.ohio-state.edu!sunybcs!sbcs!stealth!brnstnd
From: brnstnd@stealth.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.software-eng
Subject: Re: CS education [engineering, mathematics, and computer science]
Message-ID: <4092@sbcs.sunysb.edu>
Date: 30 Nov 89 02:54:38 GMT
References: <2608@fai.UUCP> <34818@regenmeister.uucp> <9924@june.cs.washington.edu> <4059@sbcs.sunysb.edu> <9963@june.cs.washington.edu>
Sender: news@sbcs.sunysb.edu
Reply-To: brnstnd@stealth.acf.nyu.edu (Dan Bernstein)
Distribution: usa
Organization: IR
Lines: 123

In article <9963@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes:
> Obviously, Dan Bernstein did not read what I wrote or did not understand it.

Peter, one of us is involved in computing a billion digits of e and knows
what he's talking about.

I'll go through these ``wrong''s one at a time. You say it's obvious
that I didn't read/understand your previous posting, but none of your
arguments are based on information in your previous posting; what do
you believe I missed?

> 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?

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

Do you distinguish between the study of measurable sets and integrable
functions and the study of different types of measures and integrals?

> 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. Measure theorists sit around
talking about Lebesgue integrals versus Daniell integrals; the more
theoretical ones think about more general classes. Your distinction is
a play upon words and does not match how people think.

(Show me a so-called ``computability'' theorist who doesn't think about
P and NP, and I'll show you a logician.)

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

Which, as I said, is what ``computational complexity theory'' used to
mean. What's wrong with my statement?

Perhaps I should have used the word ``applied'' instead of ``practical.''

> 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 travelling salesman is computability theory. e is computational
complexity theory (``applied complexity theory'' if you like).

> >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. Your ``how to do it'' versus ``how hard it is''
is silly.

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.

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

> Perhaps mathemeticians don't understand computer science.

Oh, really. I suppose you insist that Knuth is not a mathematician.

---Dan


Brought to you by Super Global Mega Corp .com