Great unknowns
Some problems are deceptively simple but can't be solved. Without them, no one's credit card would be safe.
With each passing day, we seem a step closer to comprehending the genome, gaining important insights into deadly diseases, and understanding the makeup of our universe.
But 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 - not questions of the philosophical realm (Is there a god? An afterlife?) but of the everyday computational realm.
Think of an airline trying to allocate its planes at airports most efficiently, or a
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.
So what is the value of knowing what we can't compute? Studying such problems has immense value to society. Our entire system of e-commerce depends on cryptography, which secures our credit cards and personal data based on the faith that a math problem is too difficult for hackers to solve in a reasonable amount of time.
Also, "understanding what you cannot do is often very beneficial in science because it really points the way to what you should be doing," said Sanjeev Arora, director of the new Center for Computational Intractability at Princeton University.
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. 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."
Or consider the challenge of trying to figure out a general rule that could predict what credit histories are associated with what amount of risk, given a set of individual credit histories and credit risks. Finding the pattern, Aaronson said, is at least as hard as decoding the entire system of e-commerce cryptography.
It is no surprise that computation can't explicitly explain the economic downturn or lay bare the complex systems at work in the environment. Too much is unknown. But 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.
Studying computational intractability may seem like an ideal occupation for curmudgeonly, naysaying scientists trying to dash the dreams of others, but in some ways there's a philosophical aspect to the field - a probing into the process of the "Eureka!" moment itself.
"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.
Carolyn Y. Johnson can be reached at cjohnson@globe.com. 
