Sunday, October 11, 2009

Gowers on Complexity Bounds

Timothy Gowers has apparently been thinking about the P = NP problem. I've enjoyed his series of posts on this so far, even if the details are often a little over my head. Here's a link to the first post; the others can be accessed by conventional means.

3 comments:

  1. This is the type of problem I prefer to think about as little as possible. If it turns out the P=NP then someone will try to figure out how to solve the sign problem in P. That is not something I want to do (I don't think it is possible).

    ReplyDelete
  2. I don't think anyone thinks P = NP. It's just really hard to prove that there is a problem that's in NP - P. It's fairly clear, in fact, that to prove no such algorithm exists would require new developments in math (a "new kind of proof"); therefore the problem is interesting to mathematicians. I sort of share this mentality; I'm much more interested in general proofs about algorithms than I am in actual algorithms.

    ReplyDelete
  3. Yes, I realize that. What someone is interested in is a matter of taste.

    ReplyDelete