April 27, 2008
people didnt have any real imagination about what a polynomial with high degree could do
Martin Davis on P vs NP, from the AMS Notices:
Notices: The outstanding problem in computer science now seems to be the P versus NP problem. Do you care to speculate on whether or how that will be resolved?
Davis: I have very unconventional views about that. It is taken for granted in the field that P and NP are different but that it's just much too hard for people to prove it. I think it's 50-50! I wouldn't be in the least astonished to find that P equals NP. I think the heuristic evidence that is given, when you look at it carefully, is just circular. I certainly agree that it's very unlikely that there are really good algorithms for NP-complete problems like satisfiability. But the equating of "good" with polynomial-time computability seems to me to lack evidence. People say "polynomial," but they mean with an exponent no higher than 3. I sort of see it as a reprise of the situation with Hilbert's Tenth Problem, where people didnt have any real imagination about what a polynomial with high degree could do. I was an invited speaker last summer at a meeting in Lisbon devoted to the satisfiability problem. In my talk I said that if I were a young person I would try to find a polynomial-time algorithm for satisfiability, not expecting it to be a particularly good algorithm!
Davis: Why not? I don't see any compelling reason there shouldnt be one.
Notices: But people aren't working on it from that point of view. People seem to think that P and NP are different.
Davis: Well, there is a million-dollar prize!
Notices: Is the question of whether there is a polynomial-time algorithm the correct way of measuring the difficulty of solving problems?
Davis: Well, that's really the question. Certainly theoretically the class of things for which there are polynomial-time algorithms has nice closure properties. So it's a mathematically attractive class. But the idea of identifying them with what's computationally feasible is I think the result of looking at an analogy with Church-Turing computability, which is a very successful formalization of the intuitive notion of what is calculable in principle when you don't think about resources. But it's just not a compelling analogy in my opinion.
[Here's the far too large PDF (283Mb)]
April 20, 2008
Baseball scoreboard numbers, Los Altos, CA
April 14, 2008
It's All Right With Me
Just rediscovered: Track 9 on Ella Fitzgerald's "Ella in Rome", recorded almost exactly 50 years ago, 25 April 1958: she imitates Louis Armstrong's singing.
I liked this quotation from Max Tegmark in today's NYT about the physicist John Wheeler, who died Sunday:
For me, he was the last Titan, the only physics superhero still standing.
Somewhere in Gravitation (a book I moved to the loft deep storage a couple of years ago when I thought I probably would not want to look at it againamongst all such books, I've regretted that decision the most frequentlyalthough not so much as to actually dig the book back out of its grave), Wheeler (I presume), in reflecting on why a person might not want to study physics, or be only somewhat interested in the subject, writes something like this:
Not be interested? What? This is your ONLY CHANCE!
I'd like to see if I can find that again.
April 12, 2008
After Kyle's home run
69 THULIUM: Thulium is among the most obscure elements in the periodic table. It has very few applications. Some people consider it the most useless of all naturally occurring elements, though others will rush to its defense.
April 09, 2008
Thomas Hull demonstrates the Butterfly Bomb at G4G8
Today is Tom Lehrer's 80th birthday
April 07, 2008
Everything was quite crazy at G4G8
April 06, 2008
that whole deep existential torment
* * *
Jenna Schaal-O'Connor, a 20-year-old sophomore who is majoring in cognitive science and linguistics, said philosophy had other perks. She said she found many male philosophy majors interesting and sensitive.
"That whole deep existential torment," she said. "It's good for getting girlfriends."
April 04, 2008
1) This afternoon, Buno gave me an interesting tour and presentation about what they're working on at building b. I can testify, yes, it is something extraordinary happening there.
2) Edwards Luggage defeated Sports Shop 9-0 in Palo Alto Little League baseball. Will I have a hot dog for supper for each game this season?
3) Discarded huge stack of mostly-unread magazines, and feeling good about that.
4) Looking for office space in Palo Alto.
6) Must upload more g4g8 photos to flickr.
« March 2008 | April 2008 | May 2008 »