Computer game may hold key to cracking computer codes By Lisa Lipman, Associated Press, 11/1/2000 21:12 BOSTON (AP) A simple game that's included on nearly every personal computer could hold the key to cracking complex Internet security codes.

While some people may pass hours at work mindlessly playing the game Minesweeper, mathematicians are toiling over a larger version of the game hoping to solve a math problem so confounding that an institute offered $1 million to anyone who could crack it.

The buzz began when Richard Kaye, a mathematics professor at the University of Birmingham in England, started playing Minesweeper.

''I'm always interested in games with math elements. Math and games go together brilliantly,'' Kaye said. ''I realized there was probably some nice mathematics behind it. But I didn't know what I was looking for.''

Minesweeper, which is included with the Windows operating system, is a simple game in which players try to figure out which squares of a grid contain computerized mines. A number in each square indicates how many mines are in the squares around it.

After playing the game steadily for a few weeks, Kaye realized that Minesweeper, if played on a much larger grid than exists on the computer version, has the same mathematical characteristics as other problems deemed insolvable.

That discovery provided a clue in the search for one of the mathematics world's white whales: an as-yet unproven problem known as ''P versus NP.''

The problem attempts to determine whether questions that seem to be insolvable within a reasonable period of time might actually have a relatively simple way of being solved, possibly by computer, that no one has discovered yet.

Kaye says that if someone were to figure out an algorithm for determining all combinations of mine placement in a large-scale version of Minesweeper, that person will have solved the P versus NP problem making them eligible for the $1 million prize the Cambridge-based Clay Mathematics Institute has offered to anyone who can solve it.

The discovery could have an even greater effect on the world.

''If there was a way of playing Minesweeper efficiently, then there would also be a way of cracking codes efficiently,'' Kaye said.

The Clay Mathematics Institute held a lecture Wednesday on Kaye's ideas. Ian Stewart, a research mathematician who teaches at the University of Warwick only a few miles away from Kaye, will discuss Kaye's ideas.

''It's surprising that such a simple game would put us at such a frontier of mathematics,'' Stewart said. ''But the big questions in math are not very far below the surface of everyday life.''

Stewart said that finding another problem that has the same model as other insolvable problems gives mathematicians another possible way to solve the P versus NP problem.

''It's a feature of mathematics: a slick trick for solving one will translate into a slick trick for others,'' Stewart said.

Arthur Jaffe, president of the Clay Mathematics Institute, invited Stewart to speak after learning he would be in the United States this week.

Jaffe said that he was already a fan of ''Minesweeper'' before he heard about Kaye's research. He plays the game on nights when he has trouble falling asleep and now, given the discovery, doesn't mind if his staff or his child plays the game.

''I told my 14-year-old daughter about it,'' he said. ''She was just amazed it was educational.'' http://www.boston.com/dailynews/306/region/Computer_game_may_hold_key_to_:.shtml

-- Carl Jenkins (somewherepress@aol.com), November 01, 2000