### Friday, December 20, 2002

**Rules for a Complex Quantum World**

Michael 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-Completeness

Previous 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

- 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.

We say that f *polynomial-time reduces* A to 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,1^{k}) | M is a nondeterministic machine
and M(x) accepts in k steps}
Here 1^{k} 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,1^{p(|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 Science**

Today 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 Debate**

Elsevier 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 Math**

The 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
[]