Computational intractability

It’s been a stressful week here in Lake Wobegon, but February break is finally almost upon us; now I have a chance to catch up on things from the past few days. Of course it’s always nice to see the occasional reference to mathematics in the Boston Globe, and there was an interesting article on Monday that was primarily about math, although you might not know that from the article. That’s excusable, since its topic — theoretical computer science — isn’t necessarily considered part of mathematics. Note the emphasis that reporter Carolyn Johnson places on science and scientists rather than mathematics and mathematicians:

…for some scientists, knowing what we can’t figure out is just as important.

A little-known discipline of science called computational intractability studies the boundaries of our understanding…

Johnson has interviewed several theoretical computer scientists, including Scott Aaronson, whose blog I have included in my blogroll for some years now (under Mathematics, not Science, by the way). But it would be unfair to accuse Johnson of ignoring mathematicians altogether. For example:

The Clay Mathematics Institute in Cambridge is offering a $1 million prize as part of its “millennium awards” to the person who can prove that problems that seem unsolveable given today’s computational tools are — in fact — intractable. 

Sometimes what is intractable looks deceptively straightforward. Take the challenge of making housing assignments. Imagine that there are 100 spots in dorms, and a pool of 400 students to choose from. The dean has a list of pairs of students who are incompatible and cannot appear on the final list.

“The total number of ways of choosing students 100 from the 400 applicants is greater than the number of atoms in the known universe!” the Clay Mathematics Institute wrote in its $1 million challenge. “Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force.”

Well, yes, but I think that Johnson partly misses the point. Computers can’t and won’t solve it by brute force; no one has yet figured out how to solve it by other means, so at the moment it remains intractable, but that doesn’t make it impossible. No one knows yet whether problems that are currently intractable will remain so forever — but if they become reasonable to solve by non-brute-force means they will no longer be intractable.

Despite all that, it was good to see an article about mathematics. Perhaps the million-dollar prize will attract some people; I can think of certain students of mine…

Categories: Math