Thursday, October 08, 2009

Publicity for P versus NP

On the New York Times website, John Markoff writes an article Prizes Aside, the P-NP Puzzler has Consequences motivated by my CACM article on The Status of the P Versus NP Problem. Not a bad job describing the basic problem, at least for the layman.
The issues center around a group of classic computer science problems, like the traveling salesman problem — how to figure out the most efficient route through a number of cities given certain constraints. Factoring a large number is also a good example of what is referred to as an NP problem. At present, there is no understood method for doing it in polynomial time, but given an answer it is easy to check to see if it is correct…Checking to see if any particular solution is correct is simple, but finding the best solution in the case of very large problems is infinitely difficult.
Good to see some press for this great problem and theoretical computer science in general. And getting a mention in the Times impresses my mom more than any JACM article ever could.

One of the sentences is tricky to parse.
An esoteric branch of mathematics known as algebraic geometry may offer an avenue to prove or disprove the problem, which was first outlined by Stephen A. Cook, a University of Toronto computer scientist, in 1971.
As you readers should know, while Cook (and independently Leonid Levin in Russia) first outlined the P vs. NP problem, the much more recent algebraic geometry approach is primarily due to my former U. Chicago colleague Ketan Mulmuley.

7 comments:

  1. I like the last sentence: "It’s a bit scary because we have to start learning a very difficult mathematical field."

    If ever the mathematicians made jokes about us... :)))

    ReplyDelete
  2. An esoteric branch of mathematics known as algebraic geometry

    Actually, algebraic geometry is a mainstream branch of mathematics.
    But never mind, it's just the "New york Times", nothing serious.

    ReplyDelete
  3. I think TSP and VLSI design, while easy to state, are traditional, but not ideal as examples of hard problems we can't solve. Practitioners routinely solve these quite well. Scheduling and bin packing are probably better examples where the heuristics don't come close to (provable)optimality. Breaking of crypto and perfect game playing strategies would be other press-friendly consequences of P=NP.

    ReplyDelete
  4. If ever the mathematicians made jokes about us... :)))

    Don't worry. The field of algebraic geometry, though mainstream, is still esoteric to the vast majority of active research post-tenure mathematicians.

    ReplyDelete
  5. Don't worry. The field of algebraic geometry, though mainstream, is still esoteric to the vast majority of active research post-tenure mathematicians.


    I want to make two comments.

    1. The "esotericity" of algebraic geometry mostly refers to Grothendieck's vast unrealized program of building a theory of motives. However, the kind of math involved in the program of Mulmuley et al., has to do with representation/invariant theory and classical algebraic geometry tracing its roots from Frobenius, Schur, Schubert and so on and is not esoteric et al. It is difficult, interesting and deep, but as down-to-earth as other "non-esoteric" branches of mathematics.

    2. If one thinks (as a few of us do) about the P/NP question as a question over arbitrary structures, then the classical, real, complex versions of this questions are really facets of a more universal algebro-geometric problem -- and in this sense it is really a question of algebraic-geometry, and so its solution would involve some kind of algebraic geometry. The approach of Mulmuley et al. is one such -- but that is not the sole reason why it might be useful to learn algebraic geometry to attack this problem.

    ReplyDelete
  6. Saugata Basu's post accurately describes what increasing number of systems engineers and biologists are discovering too.

    Namely, no matter what your field of research, if you raise your mathematical framework one level of abstraction, then (with surprising generality) you'll find yourself doing algebraic geometry and/or category theory.

    ReplyDelete
  7. Since Lance has brought this into the light for so many more people and because he does NOT use capital letters, I suggest we follow the Nobel committee in terms of standards and give him a Turing Award for his P-vs-NP work!

    ReplyDelete