Science | DOI: 10.1145/1400214.1400219
David Lindley

the Limits of computability

Computational complexity and intractability may help scientists better understand how humans process information and make decisions.

ThE thEor Y oF modern computing predates by a few years the modern computer itself. In 1936, while studying for his Ph.D. at Princeton University, the British mathematician Alan M. Turing devised an idealized machine that, by executing a series of instructions and storing data, could perform any imaginable computational algorithm. Further work by Turing and others pointed to an intimate connection between computability and calculability in a more conventional sense: If the solution to a problem can be written in the form of a finite mathematical recipe, then it is computable on a Turing machine.

But among computable problems, some (as George Orwell might have put it) are more computable than others. A Turing machine can avail itself of a limitless amount of memory and take as long as it needs to produce an answer. Real computers, on the other hand, have finite storage, and theoretical computability isn’t of much practical comfort for an algorithm that takes a long time—longer than the age of the universe, say—to produce an answer. Encryption methods that rely on the difficulty of finding the prime factors of a “key”—a very large number—depend on precisely that point. A guaranteed factorization algorithm is the brute-force strategy of testing all the smaller numbers in sequence until you find an exact divisor, but the size of that task increases exponentially with the number of digits in the key. For large keys, factorization is theoretically feasible but impossible in practice.

 

photoGraphy by Chris fry

Complexity theory arose in the 1960s as a way to classify the hardness of problems. Easy problems belong to complexity class P, for polynomial time, meaning that algorithms exist to produce an answer in a time that rises no faster than some power of the size of the input. Many everyday computational tasks, such as list sorting and optimization by linear programming, belong

to P. A wide variety of more demanding problems do not seem to fall into P, however, but belong to a class labeled NP. The distinguishing characteristic of these problems is that the validity of a proposed solution can be checked in polynomial time, even though there isn’t an algorithm for generating that solution in the first place. Factorization falls into this class; if you’re presented

degrees of difficulty. The most recalcitrant form a subclass named NP-complete, the salient property of which is that if you could find an efficient (that is, polynomial time) solution to any NP-complete problem, you would in effect have found an efficient solution to all NP problems. That’s because there are efficient algorithms that can turn any NP problem into a particular

 

with two numbers purporting to be the factors of a larger number, it’s easy to check the truth of the assertion.

An alternative definition of NP problems is that they can be solved in polynomial time on what’s called a nondeterministic Turing machine. This hypothetical machine branches to different computational paths at every step, giving rise to an exponentially growing tree of computations. If one path through that tree arrives at the desired result, the machine has solved the problem. For example, a nondeterministic Turing machine could perform factorization in polynomial time by testing the exponentially large number of possible divisors.

Even within NP, though, there are

instance of an NP-complete problem. Therefore, a general solution to the NP-complete problem automatically includes solutions to NP problems related to it, but a solution to the NP problem solves only some cases of the NP-complete problem.

As his “new favorite example” of an NP-complete problem, Avi Wigderson, a professor in the school of mathematics at the Institute of Advanced Study in Princeton, NJ, offers the familiar Sudoku puzzle. That might come as a surprise to anyone who has solved countless newspaper Sudokus in the time it takes to drink a mug or two of coffee, but Wigderson emphasizes that he is not talking about just the standard 9x9 grids. Sudokus can be constructed on