In honor of its 125th anniversary, Science magazine is running a series on the
top 125 questions on science that can be asked in the next 25 years. The top 25 have a detailed blurb each: all the usual suspects are there, with
one pleasant surprise:
"What are the limits of conventional computing"
... Mathematicians have shown that if you could come up with a quick and easy shortcut to solving any one of the hardest type of NP problems, you'd be able to crack them all. In effect, the NP problems would turn into P problems. But it's uncertain whether such a shortcut exists--whether P = NP. Scientists think not, but proving this is one of the great unanswered questions in mathematics....
There is also a
blurb on mining biological data, with the key point being made that this is an interdisciplinary area that requires biologists, mathematicians and computer scientists to work together.
Progress is limited by the difficulty of translating biological patterns into computer models. Network computer programs themselves are relatively simple, and the methods of portraying the results in ways that researchers can understand and interpret need improving. New institutions around the world are gathering interdisciplinary teams of biologists, mathematicians, and computer specialists to help promote systems biology approaches. But it is still in its early days.
(Via
The Loom)
This problem
ReplyDelete"How Far Can We Push Chemical Self-Assembly?"
also needs our help,
See webpage of Len Adleman's group .
Posted by Anonymous
As a computer scietist I am thrilled that these two problems have made the list. However, the blurb raises the following question: as theoretical computer scientists, is it in our interest that these problems are attributed to "Mathematicians"? I've seen this happen very often, in particular when talking about the PRIMES is in P result, Shor's polynomial time quantum algorithm for factoring and other big TCS results.
ReplyDeleteObviously, computer scientists and mathematicians know that TCS belongs somewhere in the intersection of math and applied CS, but most people do not know that. Normally I wouldn't really care about these semantics, but considering the funding crisis for TCS and our documented lack of public outreach, I think that attributing some of our community's greatest work to Mathematicians (which are considered by the public at large as different than computer scientists) might not be in our interest. Furthermore these kinds of lists have a real impact on young people who are developing a taste for science and are considering various disciplines (particularly between Math, CS and Physics).
Posted by Anonymous
This is a tricky problem. on the one hand, I feel that students need more, not less, training in mathematics before they get a degree in computer science, so aligning outselves with mathematics is not a bad thing. On the other hand, you are right in that our raison d'etre is not mathematics but computation, and there is a big difference, even if we use mathematical techhniques.
ReplyDeleteSort of like mathematical physics I guess...
However, the article does a decent job of explaining at an intuitive level what the P vs NP problem is. and I think this is the key point. Problems in string theory and what have you are really mathematical problems that lie at the core of modern physics; however there is a way of expressing them 'physically' that makes these problems 'physics problems' rather than 'math problems'. That is the distinction we need to make, that although the problems we study can be framed mathemtically, the underlying intuition is computational and (almost) physical
Posted by Suresh