Architecture
	Autos
	Commentary
	Health
	Lottery Numbers
	Obituaries
	Politics & Government
	World News Wire

	Kupcinet
	Mitchell
	Neal
	Novak
	Quick Takes
	Roeper
	Sneed
	Steinberg
	E-mail the News Staff

Finally, it does compute

July 6, 2000

BY JIM RITTER SCIENCE REPORTER

In 1968, three mathematicians dreamed up a problem for computer scientists--and boy was it a doozy.

Known as NUG30, the devilish equation had 265,000,000,000,000,000,000,000,000,000,000 possible answers. But only one was correct.

Technique that solved NUG30 has practical uses Solving NUG30 wasn't just an intellectual game. The work could have practical applications, too. It could help design drugs, hospitals and computer chips, for example. Imagine you need to design a hospital with 30 departments. You'd want to put departments with lots of back-and-forth traffic close together. You'd space departments with less back-and-forth traffic farther apart. The NUG30 team's work--developing ways to harness the Internet and use hundreds of computers to compute huge tasks--would make it much easier to figure out all the possible permutations and come up with the best layout. -- Jim Ritter

If you tested each possible answer on a computer, at a rate of a trillion answers per second, it would take 140 times longer than the age of the universe to solve the problem.

Little wonder NUG30 stumped hundreds of mathematicians and computer scientists. But using programming shortcuts and an international network of computers, a team from Argonne National Laboratory and other institutions finally cracked NUG30 last month.

It took seven days for the computers to spit out the answer, "after which there was much rejoicing," the team said on its Web site www.mcs.anl.gov/metaneos/nug30.

NUG30 is named for Christopher Nugent, who along with two colleagues posed the problem back when Lyndon Johnson was president. Most other such challenges to computer scientists have long been solved. But despite enormous advances in computers, NUG30 defied solution.

What makes the problem so difficult is the astronomical number of possible layouts. (In mathematical terms, the number is the factorial of 30, or 30 x 29 x 28 x 27 x . . . 3 x 2 x 1.)

"People didn't think it was possible to solve," said mathematician Jean-Pierre Goux of Argonne and Northwestern University. The NUG30 team also included researchers from the University of Iowa and the University of Wisconsin.

Rather than test every possibility, the team programmed computers to test only the most promising ones. This whittled the problem down to a manageable (for computers) 12 billion possible solutions.

It would have taken one fast work station seven years to calculate which of the 12 billion possibilities was the optimal answer. Instead, the team divvied up the work and sent it over the Internet to 2,500 computers at eight research institutions in the United States and Italy. Computers worked on the problem when they were otherwise idle. In effect, the network was a poor man's supercomputer.

"This is a major advance in computing," said Jorge Nocedal of Northwestern University. "The Internet is not just a repository of information, but a huge computational resource."

Many people have tried and failed to crack NUG30. One man who didn't give up was Peter Hahn of the University of Pennsylvania. He has been trying for 30 years and until a few years ago was leading the race to solve NUG30. It was frustrating to lose.

"But what can I say," Hahn said. "They're a good team, and they came up with something better."

Back to top Back to Home

Daily Southtown Digital Chicago Pioneer Press Post-Tribune Star Newspapers

[News] [Sports] [Business] [Showcase] [Classifieds] [Columnists] [Feedback] [Home]

Copyright 2000, Digital Chicago Inc.