Source: Boston Globe, Feb 2009

A little-known discipline of science called computational intractability studies the boundaries of our understanding … but of **the everyday computational realm.**

We know answers exist, but it turns out that calculating the solutions to such kinds of problems could take too long, even if all the world’s most powerful computers were to work together on them. Individual instances can be solved, but there is no general way to attack such problems efficiently, which means the “universe could have degenerated into black holes while your computer is still running,” said Scott Aaronson, a theoretical computer scientist at MIT.

By knowing what problems we can’t solve – and scientists are busy figuring out whether problems that seem intractable actually are – researchers can pursue new ways to approach problems, or come up with approximate solutions to problems.

“There are some things we just take for granted cannot be done – and intractability research tries to make it precise,” said Sampath Kannan, director for the Division of Computing and Communication Foundations at the National Science Foundation.

“As we increasingly become an information society, it’s increasingly important to understand” the limits of computation, he said.

Recognizing that value, the National Science Foundation granted $10 million last year to Arora’s center at Princeton.

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

even with complete data about complex systems, it can be hard to find the rules and patterns that are hidden in the data, simply because of the limits of computation.

“I think it does go a long way to explaining why prediction problems are hard,” Aaronson said.

“A huge reason that we’re interested in these sorts of questions . . . is the question whether creativity can be automated,” Aaronson said. “T

“**A huge reason that we’re interested in these sorts of questions . . . is the question whether creativity can be automated,**” Aaronson said. “**The kind of creativity that proves theorems or solves puzzles, or finds patterns in data**.”

With repercussions ranging from cryptography to artificial intelligence, humanity has a lot riding on the answer to the question – which remains unsolved.

“

With repercussions ranging from cryptography to artificial intelligence, humanity has a lot riding on the answer to the question – which remains unsolved.