Mathematics Professor Peter Brooksbank Awarded NSF Grant

In computer science, there are problems that are "easy" — in the technical sense — and those that are "hard," says Bucknell Professor Peter Brooksbank, mathematics, who was recently awarded part of a $320,000 collaboration grant from the National Science Foundation (NSF) to investigate a problem of mathematical symmetry that's confounded researchers for years.

Deciding in advance that a problem is "easy" is, in fact, not that easy, explained Brooksbank, as problems that superficially look similar can behave very differently.

Take, for example, the Minimal Network Problem: A bank with offices across the country wants to set up a computer network to connect them all in the cheapest way possible. The problem can be easily solved using a simple procedure: Starting at any point, you find the connection that's the cheapest and then branch out from there, making the cheapest link each time, subject to the requirement that you don't ever create a cycle. This procedural shortcut makes it an "easy" problem.

The so-called Travelling Salesman Problem, meanwhile, sounds like a similar problem on the surface, but, in fact, mathematicians have been unable to provide it with an efficient algorithmic solution in close to 100 years of study. In it, a travelling salesman preparing to depart on a sales tour of multiple cities wants to find the cheapest path to visit them all and return home again. Is there a way for him to do so other than by essentially calculating all possible routes? Strikingly, Brooksbank said, no alternative is known. It's a "hard" problem.

"While they are similar problems, one has a very easy solution and the other doesn't," Brooksbank said. "Some problems are easy in the sense that it's possible to solve any instance of the problem using an efficient procedure. A seemingly much broader class of problems consists of all those for which it's at least possible to check, efficiently, that a given solution is correct. A big open problem in computational complexity, known as the P versus NP Problem, is whether these two classes of problems are actually distinct."

In June, Brooksbank, together with fellow mathematician James Wilson of Colorado State University and computer scientists Joshua Grochow of the Santa Fe Institute and Youming Qiao of the University of Technology Sydney, received a three-year collaboration grant from the NSF to investigate a problem that, at the moment, resides in the tantalizing gray area between "easy" and "very hard". It isn't known to have an efficient solution, but neither is it thought to be a hard problem.

"I don't know if we can prove it's 'easy,' " Brooksbank said, "but what we probably can do is identify precisely what's 'hard' about it. That is, if we could find efficient solutions to these few fundamental problems, then everything else would fall into place. One of our overarching goals is to delineate what's hard about this problem — to knock over some special cases and better understand the hard parts that remain."

The problem itself is called the Group Isomorphism Problem, which asks whether two seemingly different kinds of symmetry are actually the same. While Brooksbank admits that the mathematics community is a long way from solving the problem, last December Laszlo Babai, a renowned computer scientist, made a great leap forward on a problem that's intimately connected to group isomorphism.

"For quite a long time there has been little interest in the Group Isomorphism Problem," Brooksbank said. "Standard techniques from group theory get you so far, but then you hit a wall. Recently, members of my team have developed new techniques to attack the problem and Babai's result has in some ways brought the problem back to the forefront."

The NSF grant will allow Brooksbank and his collaborators to work together, fund graduate researchers and provide support for a conference they will host focused on the Group Isomorphism Problem and symmetry in mathematics.

While tackling the Group Isomorphism Problem is highly theoretical work, the concept of symmetry has broad applications across disciplines, Brooksbank said. In computer science, identifying symmetries can make search problems more manageable, while identifying the symmetries of a molecule can provide chemists with information about its properties, from its melting and freezing point to the strength of its molecular bonds. In fact, Brooksbank and Professor Karen Castle, chemistry, recently taught an Integrated Perspectives course examining the role of symmetry in fields as diverse as engineering, biology and psychology.

"If you can understand symmetry and exploit it, you can make problems that are ostensibly very difficult much more tractable," Brooksbank said. "The whole notion of symmetry is a very central and important one."

But for all those applications, what most excites Brooksbank about the project is the chance to explore a corner of our world that remains unknown.

"It's what drives all mathematicians," he said. "It's a fairly well understood problem — easy to pose and quite general. It's really fundamental and yet we don't know the answer to it. And that's exciting to me — that we don't know."