A meta-proof

A meta-proof of P=/!=NP, from the Geomblog in 2004. (That's "equals or does not equal".)

Note that you don't need to know anything about the P vs. NP problem to find it funny.

(via Michael Trick.)

Universality theory for cranks

From the geomblog, in 2004: a meta-proof of P=/!=NP. With very slight modifications this could be a meta-proof of the Riemann hypothesis, or any other outstanding open problem in mathematics, theoretical CS, theoretical physics, or other heavily mathematical fields. The cranks work in roughly the same way regardless of the specific question.

Logic as machine language

Gil Kalai mentions a metaphor I hadn't heard of before about the foundations of mathematics:

To borrow notions from computers, mathematical logic can be regarded as the “machine language” for mathematicians who usually use much higher languages and who do not worry about “compilation.”

Of course there would be analogues to the fact that certain computer languages are higher-level than others as well. To take an example dear to me, the theory of generating functions might be at a higher level than the various ad hoc combinatorial arguments it's often introduced to students as a replacement of. I don't want to press this metaphor too hard because it'll break -- I don't think there are analogues to particular computer languages. But feel free to disagree!

Shoup: A computational introduction to number theory and algebra

A Computational Introduction to Number Theory and Algebra, online book, by Victor Shoup. (There's also a print edition, but the online PDF-book will remain freely available.) It is what it sounds like; "computational" doesn't mean "non-mathematical" but rather means that a lot of the applications are chosen with regard to their usability in computer science, specifically cryptography.

From reddit, where various commenters have pointed out things like "the author says that book is elementary but it really isn't." Of course, this is fairly common. The author actually says

The mathematical prerequisites are minimal: no particular mathematical concepts beyond what is taught in a typical undergraduate calculus sequence are assumed.
The computer science prerequisites are also quite minimal: it is assumed that the reader is proficient in programming, and has had some exposure to the analysis of algorithms, essentially at the level of an undergraduate course on algorithms and data structures.

As usual, "elementary" means something like "a smart, well-trained undergrad could read and understand it"; it's a term of art like anything else. But in some provinces of the Internet there seems to be an idea that everything should be immediately understandable to all readers at first glance. (I use Reddit for the links it gives me to interesting news, not for the comments.)

Scott Aaronson's "Great Theoretical Ideas in Computer Science"

Scott Aaronson writes on his blog that he's giving a course Great Theoretical Ideas in Computer Science. (Note that it seems impossible to see some of the course materials if you're not at MIT; I suspect this is intentional.)

He's posting his lecture notes online; see the first lecture, which addresses questions such as:
- what is a computer, anyway?
- how do you run an online gambling site, in such a way that your customers trust they're not getting cheated by your random number generators?
- how are the ancient Greek compass and straightedge a model of computation? (And why didn't the ancient Greeks know this?)

I look forward to following this.

Also, it appears that the lecture notes will be for the most part scribed by members of the class. This system is apparently widespread in computer science; why is this not done in mathematics?

What good are applications?

What We're Doing Wrong: Programming in Theory Classes, from Michael Mitzenmacher's blog My Biased Coin. Mitzenmacher claims that the standard introductory classes in algorithms don't include programming assignments; furthermore, he thinks this is bad for theoretical computer science, because non-theoretical computer scientists get the idea that theory isn't actually good for anything.

I think the theoretical computer scientists are doing it right! But I think this from a selfish point of view -- I'm taking an algorithms class that nominally requires that I have certain classes which involve programming as a prerequisite, and I don't feel lost for not having had those classes. From a less facetious point of view, I agree with Mitzenmacher, even though it would hurt me. If someone learning something new has no idea how it connects to anything they've ever learned, it's not going to stick in their brain. The human brain is not a computer -- and even if it were, that doesn't mean that throwing a bunch of random facts in it is the best way to do things.

The same statement holds, I would think, for any course in any field that covers the "theory" behind some other material. Within mathematics, for example, it's possible to teach people what a category is without giving examples of all the familiar structures they know that are in fact categories; it's possible to teach real analysis without pointing out the connections to the calculus students already know; it's possible to teach rigorous measure-theoretic probability without appealing to (often flawed, but still useful) intuition that people have about flipping coins and rolling dice and distributing objects among boxes. I'm sure my readers can provide other examples.

The complexity zoo

From bit-player (Brian Hayes): Until NEXPTIME, on the proliferation of complexity classes.

Have you ever tried to explain to your grandmother why NP is named NP? Does she get it when you say that problems labeled NP-complete are the hardest problems in NP, but NP-hard problems might be harder, and not in NP?

Yes, complexity classes are confusing. As Hayes points out, "There are hints of structure in the naming scheme". I'm not sure if that makes it better or worse. My question is: do there exist complexity classes A, B, C, and D such that the pairs of names (A, B) and (C, D) are related in the same way but the actual classes are related in different ways? In other words, does this nomenclatures have the potential for false generalizations? Hayes points out that the chemists have come up with a good systematic nomenclature for chemical compounds, of which there are many more than there are complexity classes. It's even useful if you're not a chemist; I've caught myself on occasion using the chemist's nomenclature for alkanes to describe trees. (I studied chemistry and math in college.) In particular, if I remember correctly the systematic chemical nomenclature doesn't allow false generalizations.

The trivial chemical nomenclature does, though. ("Trivial" in chemistry doesn't have the mathematician's meaning; in chemistry it means the way in which names are assigned in a one-to-one, ad hoc manner to chemical structures.) Perhaps the Right Thing to do is not to try to regularize the current nomenclature for complexity classes, but to come up with a new systematic naming system that could overlay the current one. But that might require knowing more about complexity theory than we currently do.

There's an inclusion diagram for complexity classes at the Complexity Zoo (which also exists in a wikified version here which appears to be more current.)

more on Dijkstra

A few days ago I posted a link to Edsger Dijkstra's "On the cruelty of really teaching computer science"; an anonymous commentator has pointed to the published version, which includes a series of rebuttals to Dijkstra's claim that computer science was under-mathematized. Probably the most important point made is that although it may be theoretically possible to formally prove that one's programs work:
1. mistakes are possible in proofs, just as they are in programming, and
2. engineering has historically used both the formal methods of mathematics and more pragmatic methods.

As for my claim that anthropomorphization of mathematical objects is bad, I stand by that, but that's really more a linguistic pet peeve than anything else, and I may just be saying that because I dont like the people I associate with the use of the word "guy" for mathematical objects for other reasons. That being said, evolutionarily we are used to reasoning about people, and we should take advantage of that in problem solving.

links for 2007-10-31

• Hello, India? I Need Help With My Math, by Steve Lohr, today's New York Times. The article's really about how consumer services, like business services before them, are being offshored; tutoring is just an example.


• Pollock or Not? Can Fractals Spot a Fake Masterpiece?, from Scientific American. The verdict seems to be mixed. Pollock's paintings often contain certain fractal patterns, and certain simple images look "the same" as a Pollock painting in a certain sense. The researchers argue that their work is still valid, though:
  

  "There's an image out there of fractal analysis where you send the image through a computer and if a red light comes on it means it isn't a Pollock and if a green light comes on it is. We have never supported or encouraged such a mindless view."

  
  I'd agree with them, so long as it's more likely for the metaphorical "green light" to turn on when it sees a Pollock than when it sees a non-Pollock; there's no single way to test whether a creative work is by a particular person, other than going back in time and watching them create it.


• On the cruelty of really teaching computing science, by the late Edsger Dijkstra. (I've had this one in the queue of "things I want to talk about" for a while, but I don't remember what I wanted to say, so here it is. There are a bunch of similar things which should dribble out in the near future.) But I can't resist commenting on this:
  

  My next linguistical suggestion is more rigorous. It is to fight the "if-this-guy-wants-to-talk-to-that-guy" syndrome: never refer to parts of programs or pieces of equipment in an anthropomorphic terminology, nor allow your students to do so. This linguistical improvement is much harder to implement than you might think, and your department might consider the introduction of fines for violations, say a quarter for undergraduates, two quarters for graduate students, and five dollars for faculty members: by the end of the first semester of the new regime, you will have collected enough money for two scholarships.

  
  I've long felt the same way about mathematical objects. There are exceptions, but for me these are mostly exceptions in which the mathematics describes some algorithm that has input which is actually coming from somewhere. Here it's not so much the program that is getting anthropomorphized as the user.
  
  And why are they always "guys"? How is it that scribbles of chalk on a blackboard, or pixels on a screen, can have gender? Note that I am not suggesting that mathematical objects should be female, or that some of them should be male and some of them should be female, with the choice being made, say, by the flipping of a coin. (Incidentally, the description of mathematical objects as "guys" seems to be much more common at my current institution than at my previous one.)
  
  By the way, Dijkstra is saying here that he thinks computer science should be taught in a formal manner -- proving the correctness of programs alongside actually writing them -- and that to de-emphasize the pragmatic aspect, students shouldn't execute their programs on a computer, since doing so enables them to not think about what the program is doing. I'm not sure if I agree with this.