This work is licensed under a
Creative Commons License.
|
Friday, December 20, 2002
Rules for a Complex Quantum WorldMichael Nielsen has a recent Scientific American article giving a very readable view of quantum information and computation. Nielsen is also co-author with Isaac Chuang of Quantum Computation and Quantum Information, the best book I've seen on the topic.
9:48 PM # Comments []
Thursday, December 19, 2002
Foundations of Complexity
Lesson 11: NP-CompletenessPrevious Lesson | Next Lesson
Informally, NP-complete sets are the hardest sets in NP. What does it mean to be hardest? Here we use a polynomial-time version of reduction, a concept we first saw in Lesson 5.
Formally a language L is NP-complete if
We say that f polynomial-time reduces A to L.
- L is in NP, and
- For all A in NP, there is a polynomial-time computable function f such that x is in A if and only if f(x) is in L.
The following theorem captures the intuition for NP-completeness.
Theorem: Let L be an NP-complete language. Then L is in P if and only if P = NP.Proof: If P = NP then since L is in NP then L is in P. Suppose L is in P and A is in NP. Let f be the reduction from A to L. We can then determine whether x is in A by testing whether f(x) is in L. ◊
In particular if any NP-complete set has an efficient algorithm then all NP-complete sets have efficient algorithms.
Do there exist NP-complete sets? Here is an example:
L = {(<M>,x,1k) | M is a nondeterministic machine and M(x) accepts in k steps} Here 1k is just a string consisting of exactly k 1's.L is in NP by just simulating M(x) for k steps. If A is in NP, then A must be accepted by some nondeterministic machine M using time p(|x|) for some polynomial p. The reduction f is just f(x)=(<M>,x,1p(|x|)).
L is not a natural language; you are unlikely to see it come up in any real-world application. In future lessons we will see that a large number of truly natural search problems are NP-complete which is why NP-completeness is perhaps the single most important concept to come out of theoretical computer science.
2:32 PM # Comments []
Wednesday, December 18, 2002
Ramsey Theory and Computer ScienceToday we have a guest post from William Gasarch.
How many papers apply Ramsey Theory to Computer Science? If you said 37 and 4 surveys then you've probably visited www.cs.umd.edu/~gasarch/ramsey/ramsey.html where William Gasarch has a collection of such. A prominent theorist thinks there are over 100. Rather than argue the point, see if your favorite paper that applies Ramsey Theory is there, and if not then email the reference and if possible the paper or a link to it, to gasarch@cs.umd.edu.
6:15 PM # Comments []
Tuesday, December 17, 2002
The Great Journal DebateElsevier is closing down IDEAL the electronic access point for Academic Press, a publisher recently acquired by Elsevier. This leaves only Elsevier's Science Direct for electronic access of the Academic Press and other Elsevier journals. Given this news and today's New York Times article I feel I should comment on the great journal debate. As a member of the editorial board of Information and Computation, one of the Academic Press journals, these issues give me some angst.
The internet has, of course, a large effect on the distribution of scientific papers over the last ten years. Even more so, the consolidation of the scientific publishing companies has put a squeeze on university libraries.
Many of my colleagues have suggested that we just start up our own online journals. Running a journal is more than just getting papers refereed and sticking them on a web page. Journals have to be marketed, maintained and presented in a format that makes information easy to find. The private companies do a very good job of this. However, Elsevier's recent pricing policies are causing many libraries to drop several of their journals. Loss of access is never a good thing.
The professional societies, such as ACM, IEEE and SIAM have their own journals with their own on-line access policies that might form a reasonable median. You can also often get early versions of papers from scientist's home pages or sites like citeseer.
I have mixed emotions on the whole journal issue. Clearly status quo is not working--something will have to give. My biggest fear is that scientists will just stop submitting to journals altogether. I don't believe this is the best way to maintain knowledge for generations to come. After all, who will maintain your web page a century from now?
10:28 AM # Comments []
Sunday, December 15, 2002
Outsider MathThe New York Times Magazine today highlights a year full of ideas, one of which is on the Agrawal et. al. primality algorithm under the title "Outsider Math". While Manindra might not have been an expert in number theory he was already an established member of the computational complexity community--certainly not an outsider in my mind.
8:38 AM # Comments []