any doubly square grid—16x16, 25x25, and so on—and the crucial point is that although many Sudokus may be easy to solve, no algorithm exists to solve an arbitrarily large Sudoku in polynomial time.
Showing that a problem is NP-complete means proving that no known algorithm can solve it in polynomial time. But does that mean no such algorithm exists, or that no one has invented one yet? Is the class NP, in other words, truly different from P? So fundamental is this question that it has the distinction of being one of the seven Millennium Problems whose solution the Clay Mathematics Institute in Cambridge, MA, has deemed worthy of a million-dollar prize. The majority opinion among mathematicians and computer scientists is that NP is not identical to P, says Sanjeev Arora, a professor of computer science at Princeton University, which would mean that NP problems are genuinely hard and that in all likelihood no easy method for factorization exists. However, no proof currently exists.
Complexity theory has become immensely sophisticated, to the point that there are now close to 500 distinct complexity classes, distinguished by mathematical niceties of the methods that will solve them. This classification is far more than an abstract exercise, however. Understanding a task’s computational complexity can provide a novel perspective on real-world processes in which a task shows up.
One “hard” problem not in NP is the computation of so-called Nash equi-
libria, which arise in game theory and economics. A Nash equilibrium exists where each participant in a multi-play-er game is using an optimal strategy, taking into account the strategies used by the other players. That is, no single player can make a unilateral change that will improve his or her outcome. It’s recently been proved that the computation of Nash equilibria is complete for its class, known as PPAD, which means that a way to compute them efficiently would also solve other hard problems.
Nash equilibria crop up in the study of distributed decisionmaking, where parts of a system act as independent agents that determine the behavior of the system as a whole. As such, they are of great interest to economists, but their computational intractability raises the question of whether and how real markets actually compute Nash equilibria, or whether the types of Nash equilibria that arise in economics are of a simpler and more tractable kind.
These notions of hardness rest on the assumption that the Turing machine is a universal model for all methods of computation. That seemed like a safe bet until quantum computing came along. The bits in a quantum computer, known as qubits, can exist in superpositions of many states at once, as the strange rules of quantum mechanics allow. The operation on a single qubit can, in effect, perform many computations at once, and in 1994, MIT mathematics professor Peter Shor made use of this property to devise a quantum computer algorithm for factoring numbers in polynomial time.
It remains uncertain whether it is feasible to build quantum computers of sufficient size to do interesting factorizations. Moreover, Wigderson says, a quantum computer is not a nondeterministic Turing machine, because purposeful manipulations of qubits are not equivalent to unrestricted exponential branching. Shor’s factorization algorithm, which relies on certain properties of prime numbers in order to select the desired answer from the multiplicity of superposed computations, may be a special case. “There’s no hint that quantum computers can solve any NP-complete problem,” Wigderson adds.
Beyond its significance for computation in the formal sense, Wigderson says that complexity theory sheds light on our intuitive idea of what it means to call a problem hard. He suggests that the characteristics of a NP problem—a solution cannot be obtained by any routine method, but when found is easily checked—are reminiscent of what happens when a scientist hits on a theoretical innovation that
china will significantly increase production of its godson microprocessor and plans to build its first petaflop supercomputer in 2010, according to PC World.
china decided against investing in microprocessor development in the late 1980s, but changed course in 2001. its chip technology currently lags behind that of AMd, iBM, and
intel, but china multiplied its investment in chip production in 2006 and now has four different godson processors. A deal was struck with stMicroelectronics last year to manufacture and sell the chips under the commercial name of Loongson, and the chips are being used by 40 companies in laptops, set-top boxes, and other devices.
due in 2009, the godson 3
chip will be china’s first
multicore chip, with four
general-purpose cores and four
specialized cores for tasks such as
scientific computing, advanced
technologies, and national
security. china plans to use the
godson 3 chip in its proposed
one-petaflop supercomputer.
if china succeeds, the godson
3-powered supercomputer will
match the performance of the
iBM roadrunner system, which
leads this year’s top500 list of the
world’s fastest supercomputers.
Built for the u.s. department of
Energy’s national nuclear security
Administration, the roadrunner
system has a processing speed
of one quadrillion calculations
per second and is used for
research into astronomy, climate
change, energy, and nuclear
weapons simulations.
References:
Archives