P, NP, and Mathematics
Avi Wigderson has just posted the paper based on his forthcoming ICM plenary lecture.
I suggest you stop doing whatever you are doing (I mean, come on, you are reading a blog, you can't be too busy...) and read it now.
In August, Avi will bring the lieta novella of the P versus NP question (and of complexity theory in general) to, literally, thousands of mathematicians: ICM 2002 in Beijing was attended by more than 4,000 people, and many of them went for the conference not just for the food.
This will be an important turning point on how other mathematicians look at what we do. Even now, of the latest generation of pure mathematicians, those who like problem-solving more than theory-building (and who naturally gravitate around analysis, combinatorics, analytic number theory and probability) can be very sophisticated in their appreciation of complexity, and, I think, they see it as one of those parts of pure mathematics that one should know something about, even if one does not work on it.
When Terence Tao (analyst, number theorist, and combinatorialist of "primes in arithmetic progression" fame and likely 2006 Fields Medalist) visited Berkeley, we talked for some time and he asked a few questions. "When you have a subset of the hypercube whose Fourier spectrum is concentrated on a few Fourier coefficients, is there a way to find them without looking at the whole hypercube," yes, it's the Goldreich-Levin theorem (he wanted to see the proof, we went through it in about five minutes); "if P!=NP, would this settle the question of whether there are problems that are hard on average?" It's unlikely; "is it plausible to use Fourier analytic techniques to study the circuit complexity of functions?" not for general circuits, because of Razborov-Rudich (he had heard of it before, and he wanted to know what exactly is the statement of Razborov-Rudich).
If you have enough time to read my Beijing restaurant reviews, you also have enough time to read this article by 1998 Field Medalist Tim Gowers titled "on the importance of mathematics." The P versus NP question figures quite prominently. Since you are at it, you may try to find the video of his talk at the Clay Institute web site (the link from Gowers' page is broken) [Update the talk is available at http://claymath.msri.org/gowers2000.mov] on the same topic. And, I don't mean to boss you around, but you should also buy and read this book, a masterpiece of mathematical exposition for the general public. (Circuit complexity and NP-completeness are featured.)
I suggest you stop doing whatever you are doing (I mean, come on, you are reading a blog, you can't be too busy...) and read it now.
In August, Avi will bring the lieta novella of the P versus NP question (and of complexity theory in general) to, literally, thousands of mathematicians: ICM 2002 in Beijing was attended by more than 4,000 people, and many of them went for the conference not just for the food.
This will be an important turning point on how other mathematicians look at what we do. Even now, of the latest generation of pure mathematicians, those who like problem-solving more than theory-building (and who naturally gravitate around analysis, combinatorics, analytic number theory and probability) can be very sophisticated in their appreciation of complexity, and, I think, they see it as one of those parts of pure mathematics that one should know something about, even if one does not work on it.
When Terence Tao (analyst, number theorist, and combinatorialist of "primes in arithmetic progression" fame and likely 2006 Fields Medalist) visited Berkeley, we talked for some time and he asked a few questions. "When you have a subset of the hypercube whose Fourier spectrum is concentrated on a few Fourier coefficients, is there a way to find them without looking at the whole hypercube," yes, it's the Goldreich-Levin theorem (he wanted to see the proof, we went through it in about five minutes); "if P!=NP, would this settle the question of whether there are problems that are hard on average?" It's unlikely; "is it plausible to use Fourier analytic techniques to study the circuit complexity of functions?" not for general circuits, because of Razborov-Rudich (he had heard of it before, and he wanted to know what exactly is the statement of Razborov-Rudich).
If you have enough time to read my Beijing restaurant reviews, you also have enough time to read this article by 1998 Field Medalist Tim Gowers titled "on the importance of mathematics." The P versus NP question figures quite prominently. Since you are at it, you may try to find the video of his talk at the Clay Institute web site (the link from Gowers' page is broken) [Update the talk is available at http://claymath.msri.org/gowers2000.mov] on the same topic. And, I don't mean to boss you around, but you should also buy and read this book, a masterpiece of mathematical exposition for the general public. (Circuit complexity and NP-completeness are featured.)
posted by Luca at 5:40 PM
0 Comments:
Post a Comment
<< Home