Monday, November 21, 2005

A short proof that a proof is probably wrong

Here's another attempt at separating NP from P, this time from the backwaters of beautiful Ernakulam in Kerala, India. The title says "NP != P and CO-NP != P", whence it follows that the proof is almost surely wrong. No self-respecting mathematician would've written the second part of the title.

(For the programming-languages-challenged, "!=" is the same as $\neq$)

Sunday, November 13, 2005

The evolution of religious criticism of science

The Pope on Creation: (from the AP. No surprises here)
Pope Benedict XVI has waded into the evolution debate in the United States, saying the universe was made as an "intelligent project" and criticizing those who say its creation was without direction. .... He quoted St. Basil the Great as saying that some people, "fooled by the atheism that they carry inside of them, imagine a universe free of direction and order, as if at the mercy of chance."
Op-Ed: Our Faith in Science by Tenzin Gyatso, the 14th Dalai Lama.
This is very interesting, for in the middle of an otherwise thoughtful, balanced and progressive article, the Dalai Lama slips in this scary sentence:
Yet the ramifications of [the progress in science, esp. genetic manipulation] are such that it is no longer adequate to say that the choice of what to do with this knowledge should be left in the hands of individuals.
I am really curious about what alternatives he has in mind.

Alarmist articles!

One more alarmist article about how the U.S. might be losing its "competitive edge" in "innovation" -- worries ranging from how science is not emphasized enough in grade school to how Singapore and China grant more PhDs in science and engineering than the US.

I just don't get it. Why is it bad for the U.S. if the rest of the world makes significant advances in science and technology? On the contrary, I believe it is good for everyone, especially the U.S. As newer and newer innovations take place, they often tend to become interdependent -- a giant example is how personal computing, wireless communications, and the Internet are coming together in ways we might not have seen a decade ago. When these interdependencies grow, there will be significant opportunities for the U.S. both in terms of business deals and in terms of scientific exchange.

A case in point: India. While I was growing up as a teenager in India, there was much concern within India about "brain drain" -- about how a large number of the top students from Indian institutions routinely left for higher studies in the U.S., and how it was going to undermine India's investment in science and technology education. This notion seems almost silly today. A good deal of India's "modern economy" is built around the computing services sector, thanks in large part to being tuned in to the advances in computer science elsewhere (primarily the U.S.).

I hope the alarmists will shed their paranoia and instead celebrate the fact that more and more of the world is joining the culture of innovation and advanced science and technology. It just might be good for all of us.

Wednesday, November 02, 2005

Popular CS Books, or lack thereof

In an IM conversation, Ravi Kumar of Yaho
o! Research points out that there aren't any "popular" computer science books -- there isn't a Timothy Gowers or E.T. Bell or Brian Greene or Richard Dawkins. (When I invited Ravi to write a guest blog article on this subject, he promptly backed out, though -- another reluctant writer within our ranks :-)

I wonder why. Oxford Press' "Very Short Introduction" series has nearly 30 titles in the "Science" section, including such topics as "Philosophy of Science" and "Jung" and "Consciousness", but none on the science of computing. There's one on cryptography, but I am quite certain no two scientists who consider themselves cryptographers will agree on what ought to be in a book with that title :-). Absolutely nothing on the "Internet" or "Algorithms" or even "Artificial Intelligence", a favorite among the non-scientific audience. John Battelle's "Search" has made it to under-200 on the Amazon sales rank, but that's more of a meta-CS book (historical anecdotes, biographical stories, business wisdom, etc.) than an actual CS book.

Even the mighty Christos Papadimitriou's "novel about computation" Turing doesn't seem to have made a dent (if it's any indication, his "Computational Complexity" book sells more on Amazon than does Turing). Noam Nisan has a new book "The Elements of Computing Systems: Building a Modern Computer from First Principles" (with Shimon Schocken), which I haven't seen yet (reviews welcome as comments!). From the blurb on Amazon, this seems to be more of a course textbook; don't expect it to become an NYT #1 seller in the nonfiction category.

Why isn't there a popular book talking about how some early computer scientists like Turing and von Neumann had tremendous foresight and got some basic "design decisions" right (like universal machine, stored program computer, etc.)? If there's a CS book for the masses, what, gentle reader, would you like to see in it?