PORTLAND, Ore. — Combinatorial problems are one of the toughest nuts to crack in design automation and other applications that sift data. For instance, the number of Internet router path combinations for sending a message around the world is enormous. The shortest path is seldom chosen because there is no way to find the optimal distance among so many possibilities.

Now, the developers of an algorithm called "Saucy" claim it can solve such problems quickly by finding symmetries among large swaths of possibilities. In the global Internet routing problem, Saucy found so many symmetries--10 with 83,687 zeros--that it could sort through and an find an optimum path in under a second. Saucy was described this week at the Design Automation Conference.

"Our software calculates symmetries, but of course it does not list them out--the representation Saucy finds is implicit--a few hundred or thousand or tens of thousands of symmetries are enough to implicitly represent an entire set," said Paul Darga, engineering doctoral candidate at the University of Michigan.

Symmetries are mathematical equivalent branches of a search--interchangeable options that lead to the same outcome and, thus, only need to be calculated once. By identifying all the symmetries in a set before comparing them, the number of possibilities is vastly reduced.

Called graph automorphism, a core problem in computer science, many solutions have been proposed, but University of Michigan researchers claim Saucy solves even million-variables problems in seconds--even when current methods might take days.

"We have sped up symmetry detection so much that it's almost instanteneous," said Markov. "And it does not hurt even when there is no solution."

An example is fitting 10 pigeons into nine pigeon holes--a problem with no solution. There are an enormous number of combinations of trying to fit 10 birds in nine holes, and even though the problem has no solution, a conventional exhaustive-search algorithm must check each possibility. By contrast, Saucy first recognizes a nine-fold symmetry (because holes are interchangeable) as well as a 10-fold symmetry (because the birds are interchangeable), and thus only has to do a single evaluation to quickly conclude there is no solution to the problem.

The researchers claim the Saucy algorithm applies to many other applications, ranging from cracking tough scientific problems and identifying bugs in software and hardware designs to verifying the safety of train schedules. '