While computers are exponentially more powerful and increasingly important in both society and in every area of scholastic inquiry, modern computers appear to be incapable of solving certain problems. In recent decades, computer scientists have begun to develop an understanding of what makes some computational tasks “intractable” not just for current computers but for all foreseeable computers, even if they were joined together.

Princeton is the lead institution for a new $10 million National Science Foundation grant for the study of computational intractability. At the Dec 10 Lunch ‘n Learn seminar, Sanjeev Arora, the principal investigator on the new grant, Professor of Computer Science, the Director of the Center for Theoretical Computer Science, and the Director of the Center for Intractability gave an overview of both the field and what the new center is trying to accomplish.

The study of computational intractability has implications for many scientific fields and may also yield positive benefits in a broad range of areas. Arora began by thinking about a simple, combination lock with 40 numbers on the dial. Why is it secure? To pick it, a thief would have to stumble upon a single solution within 40³ or 64,000 combinations. Adding additional rotations exponentially augments security. The same lock involving 50 rotations, would have more possible combinations (40⁵⁰) than there are atoms in the universe and would defy any computational setup.

Such exponential schemes occur in many scenarios. The key question, which rests at the heart of computer science, is P vs NP. Are there problems that are impossibly hard, computationally intractable, or are they solvable through brilliant deduction?

In examples of Diophantine equations that involve exponential, 2ⁿ solutions, finding the answer is, as in the case of the combination lock, looking for the “needle in a haystack” despite the fact that it is easy to verify the solutions. Such computational problems are classified as “NP”. The key, of course, is to try to avoid exhaustive searches and to try to solve NP problems efficiently (in “P”).

Consider the computational problem underlying this question: given a diopantine equation, decide if it has a solution over the integers. Matiyasevich showed in the 1960s that no computer can solve this problem. For hundreds of years, no human or computer solved Fermat’s last theorem until Andrew Wiles proved that there is no solution. No computer, says Arora, can derive solutions to such Diophantine equations which involve integers as solutions. It took brilliant mathematicians three centuries to solve one equation.

For many difficult problems, there are clever algorithms that circumvent conventional trial and error searching. The P vs NP question is, of course, can we efficiently avoid exhaustive needle in a haystack searches. The traveling salesman problem, which has roots in the 19^th century, involves whether there is an optimal path connecting n points. Once again, the number of possible paths becomes exponential and quite intractable as we move into multiple dimensions. Scheduling final exams (or airline flights) also falls into the same category. Imagine n students, k classes, m time slots, and a need to minimize time conflicts.

If P=NP, says Arora, then brilliance becomes routine. We will then regularly determine the best route, the best schedule, the best design, and the best proofs. If P≠NP, then we have learned something new and fundamental not just about computers but about the world.

Complex processes, from general equilibrium theory in economics, the folding of proteins, and even how natural orgasms like birds, fish, and even bacteria self-organize are all algorithmic. For example, in the economy, no known algorithm computes general equilibrium, the system of prices for every good, but the market effortlessly computes it. It is possible that our models of nature need for testing; or, says Arora, it may be that nature solves problems only approximately, not optimally.

The research is essential for many real life problems including cryptographic schemes, more secure e-voting, e-commerce, and even quantum computing, an effort to build computers by harnessing the physical properties of sub-atomic particles. Concludes Arora: “Computer algorithms are anew language for science. Understanding their limitations will lead to new science and new applications.”

A podcast and the presentation are available.

Posted by Lorene Lavora