Xref: utzoo comp.software-eng:2580 comp.theory:96
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!swrinde!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,comp.theory
Subject: Re: computational complexity (was: CS education)
Message-ID: <4115@sbcs.sunysb.edu>
Date: 2 Dec 89 06:48:11 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> <10014@june.cs.washington.edu>
Sender: news@sbcs.sunysb.edu
Reply-To: brnstnd@stealth.acf.nyu.edu (Dan Bernstein)
Distribution: usa
Organization: IR
Lines: 98

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


Brought to you by Super Global Mega Corp .com