I see your distinction, but I don’t think it’s useful. Once you’ve got a set of axioms (as theoretical computer science does), the proving of theorems is a mathematical process. While it may be applied math, it’s a math problem, stated in mathematical terms and attacked by mathematical methods.
Devlin says of the P vs. NP problem:
Technically speaking, as far as I understand it, this millennial problem is still purely mathematical and not computer science at all.
Here’s a pretty complete listing of Essays by Isaac Asimov about mathematics and computers. There are a few titles that mention math, but I have just about all 399 of his F&SF columns in the original magazines and they’re about numbers when you come right down to it.
Exapno Mapcase’s quote of Devlin highlights the issue quite strongly. The most prominent “Mathematician” working on those problems was Turing. And he most definitely was quite serious about building actual computers. First, special purpose computers during WWII and then general purpose machines afterwards.
The term “Computer Scientist” did not exist then. Turing is a Computer Scientist.
I know of no value that the answer to P vs. NP would have to Mathematicians. But to Computer Scientists (and many other practical people), it would be Big News.
Compute Scientists use Mathematics. So do Biologists and Chemists. Sometimes we even nudge Mathematics along to get somewhere. Axioms, trigonometry, Bayesian statistics, they are all tools. Which field you are in determines which tools you use. Not the other way around.
I have published hundreds of Theorems, Corollaries and Lemmas over the years. Not a single one advanced Mathematics in any way whatsoever. It’s using a language, not creating one.
Using ftg’s post as a jumping point and going off-topic…
What’s the value of solving these 7 Millenium problems, apart from the intrinsic mathematical interest?
Is it that mathematicians already have an intuition about the “answers”, but don’t have a proof? Or, are the answers themselves not “known” ?
What would be the real world applications of solving say, the Poincare conjecture?
It’s not uncommon for mathematicians to have little to no interest in real world applications of their work. The main reason these problems are interesting (aside from P vs. NP, and the physics one) is because a lot of people have tried to solve them and failed. It may be that we gain nothing but understanding from them, but for us, that’s enough.
And that’s why ftg’s issue of value just doesn’t mean that much to me. It’s possible that the question of whether P = NP is undecidable–neither a proof nor a counterexample will be found–but even learning that would be a step ahead of where we are now. For me, and many others, that’s enough.
There’s really two kinds of Computer Science: practical and theoretical. Most people learn about practical computer science: programming, websites, etc. Theoretical computer science is VERY mathematical: theory of algorithms, image analysis, etc.
ccwaterback, Is website designing, really a computer science (practical or not)? Same goes for programming, learning the syntax and some conceptual/procedural constructs?
I’ve always understood Compter Science to be the theoretical stuff.
It’s probably just a matter of semantics. I would say most universities list programming and website design under computer science, but I see your point.
Maybe “Information Systems” is a better label for programming, websites, etc. I see a lot of schools with information systems (sub-) departments these days. That way, Computer Science is indeed the mathematical, theoretical field.
I am a Theoretical Computer Scientist. I have taught Theory so many times …
And it is quite obvious to me that the stuff I taught uses a little bit of Math, but doesn’t actually do Math.
At the research level, some people use slightly advanced Math, but generally not much. In my area, e.g., there was one paper that cited some classic facts from Ramsey Theory, but it didn’t really get them much. The most advanced Math stuff used in my area involves a tiny bit of Algebraic Topology. Stuff you would skim thru in the first couple weeks in a grad course on it. But no one has created new results in Algebraic Topology in my area.
In all my years working at universities, I have never met a single Math prof that was the least bit interested, or even informed, about anything going on in Computer Science with one exception: Numerical Methods (CS)/Analysis (Math). And even then there was usually a vast divide. The CS types wanted efficient results, the Math types wanted to prove error rates (and believed the most ridiculous nonsense as to what constituted “good” algorithms).
So, who’s best equipped to solve the P vs. NP problem? A comp-scientist or mathematician?
Louis Lyons:
“All you wanted to know about Mathematics but were afraid to ask - Mathematics for Science Students”.
Volume 1 + Volume 2
Impressed me that much, that I wrote a thank you email to the author …
flonks
Thanks for the recommendation. From Amazon’s entries, it seems that these are mathematics books, not books about mathematics. Nonetheless from the editorial reviews, these might be useful anyway.
Not exactly what you asked for, but quite comprehensive.
Look for a copy of “The World of Mathematics” by James R. Newman, Simon snd Shuster, New York, 1956. in 4 volumes, about 2500 pages.
“a small library of the literaturre of mathematics from A’h-mose the Scribe to Albert Einstein, presented with commentaries and notes by J.R.N.”
This is a damn shame, and needs to change.
I know this is a bit late, but T.W.Korner’s book “The Pleasures of Counting” is a really good general read, and fulfills most of the OP’s requirements. I have a copy sat on my bookshelf at home, and I love it!
You have it exactly reversed. Mathematicians don’t give a damn about the “value” of their problems: P vs. NP has exactly the same value to a mathematician as does the Greater Goldbach Conjecture, or the Riemann Hypothesis, or the like. But computer scientists (the ones who aren’t mathematicians, that is) do care about practicality and “value”.
Now, suppose that P vs. NP is resolved. On the one hand, it might be proven that P != NP. Which would have no practical impact at all, since that’s what all computer scientists assume anyway. On the other hand, suppose someone finds an algorithm for the Travelling Salesman problem that scales as x to the 19,473rd power. That would prove that P = NP, but such an algorithm, despite being quadratic, would still be slower than the existing exponential ones for all practical applications. Neither result would be interesting to a computer scientist, but both would be interesting to a mathematician.
I’ve been reading Roger Penrose’s “The Emperor’s New Mind” lately. Yeah, I instantly get into territory that is over my head, but you folks ought to do fine.
Let me recommend ARCHIMEDES REVENGE : The joys and Perils of Mathematics. by Paul Hoffman . A nice general read.
A CS person by far, by very very far. You can put a typical Math person into the same category as a Chemist or Biologist in this regard.
And, you could walk up to a typical Math prof, tell him that P vs NP has been solved and 9 out of 10 won’t even bother to ask which way it went. And 10 out of 10 won’t work on any implications of the result. There are hundreds of similar open problems in Computational Complexity. After P vs NP is solved, the next one will be solved by a Computer Scientist, and the next, and the next. Hardly any Mathematician has even heard of #P vs. PH.
It is also most definitely not true that CS folk are certain that P != NP. There are reasons for doubts, there have been surprising “it went the other way!” results, such as NSPACE closed under complement. Many an expert has said that they could solve P vs. NP is no time if they only knew for sure which way it went.
Chronos: You meant “polynomial”, not “quadratic”. It is one of the niceties of nature that it is rarely perverse. An unusual exponent (forget size, what if it’s 5.7316?) for SAT isn’t going to happen. Once a polynomial bound, any exponent, is found, people quickly find better ones. Take Network Flow. The first algorithms had fairly ugly bounds. They kept getting better. Very simple, small bounds now. That’s the way these things go. A similar specious argument along these lines are also made against the use of Big Oh.
One thing to keep in mind in these CS vs. Math issues is the politics. For the last 3 decades, CS has grown tremendously while Math has shrunk. The Math dept. at a place I had once worked at actually had it’s grad program shut down since they just weren’t getting any students or funding. Tenured faculty lost jobs. So politics gets thrown into all this.
Getting back to the OP. I read all the usual well recommended Math books and find almost all of them appalling. There are great Math populizers out there. Conway is a hoot. An amazing speaker. But he is not a Big Time Book author. Maybe they ought to do a “Conway Lectures” of videos.
There are several things that make Math a very insular field, and hard to popularize. Many Scientists get too focused on just their sub-sub-area and don’t know or care about what else is going on. But many have broader interests, I certainly do. Math people are much worse in this regard. Also, I can pick up an issue of Science or Nature and understand the abstract of most papers. I can even read and “get” quite a bit of many papers. Not so with Math papers. Extremely obtuse writing style.