Nanotechnology Now - Press Release: A new kind of counting: Göttingen-based scientists are developing a computer algorithm to solve previously unsolvable counting problems

Home > Press > A new kind of counting: Göttingen-based scientists are developing a computer algorithm to solve previously unsolvable counting problems

Fig. 1: Left and center: A map of Germany with corresponding representation as a network. Top right: A simplified sudoku with three rows of three boxes. Bottom right: The representation as a network. "1" is represented in "red", "2" in "blue" and "3" in "yellow".

Image: Max Planck Institute for Dynamics and Self-Organization

Abstract:
How many different sudokus are there? How many different ways are there to color in the countries on a map? And how do atoms behave in a solid? Researchers at the Max Planck Institute for Dynamics and Self-Organization in Göttingen and at Cornell University (Ithaca, USA) have now developed a new method that quickly provides an answer to these questions. In principle, there has always been a way to solve them. However, computers were unable to find the solution as the calculations took too long. With the new method, the scientists look at separate sections of the problem and work through them one at a time. Up to now, each stage of the calculation has involved the whole map or the whole sudoku. The answers to many problems in physics, mathematics and computer science can be provided in this way for the first time. (New Journal of Physics, February 4, 2009)

A new kind of counting: Göttingen-based scientists are developing a computer algorithm to solve previously unsolvable counting problems

Munich, Germany | Posted on February 13th, 2009

Whether sudoku, a map of Germany or solid bodies - in all of these cases, it's all about counting possibilities. In the sudoku, it is the permitted solutions; in the solid body, it is the possible arrangements of atoms. In the map, the question is how many ways the map can be colored so that adjacent countries are always shown in a different color. Scientists depict these counting problems as a network of lines and nodes. Consequently, they need to answer just one question: How many different ways are there to color in the nodes with a certain number of colors? The only condition: nodes joined by a line may not have the same color. Depending on the application, the color of a node is given a completely new significance. In the case of the map, "color" actually means color; with sudoku the "colors" represent different figures.

"The existing algorithm copies the whole network for each stage of the calculation and only changes one aspect of it each time," explains Frank van Bussel of the Max Planck Institute for Dynamics and Self-Organization (MPIDS). Increasing the number of nodes dramatically increases the calculation time. For a square lattice the size of a chess board, this is estimated to be many billions of years. The new algorithm developed by the Göttingen-based scientists is significantly faster. "Our calculation for the chess board lattice only takes seven seconds," explains Denny Fliegner from MPIDS.

This is how it's done: With the new method, the researchers move through the network node by node. As if the computer program were short-sighted, it only ever looks at the next node point and not at the whole network. At the first node point, it cannot finalize the color selection as it would have to know how all the other nodes are connected to each other. However, instead of answering this question, the program notes down a formula for the first lattice point which contains this uncertainty as an unknown quantity. As it progresses through the network, all the connections become visible and the unknown quantities are eliminated. Having arrived at the final node point, the program's knowledge of the network is complete.

This new method can be used on much more complicated cases than the existing standard algorithm. "We can now answer many questions in physics, graph theory and computer science that have hitherto been practically unsolvable," says Marc Timme from MPIDS. "For example, our method can be applied to antiferromagnetic solids," he adds. In these solid bodies, every atom has an internal rotational pulse, called spin, which can have different values. Usually, adjacent atoms exhibit different spins. It is now possible to calculate the number of possible spin arrangements, which will allow physicists to draw conclusions about the fundamental characteristics of the thermodynamics of solid bodies.

####

About Max Planck Society
The research institutes of the Max Planck Society perform basic research in the interest of the general public in the natural sciences, life sciences, social sciences, and the humanities. In particular, the Max Planck Society takes up new and innovative research areas that German universities are not in a position to accommodate or deal with adequately. These interdisciplinary research areas often do not fit into the university organization, or they require more funds for personnel and equipment than those available at universities. The variety of topics in the natural sciences and the humanities at Max Planck Institutes complement the work done at universities and other research facilities in important research fields. In certain areas, the institutes occupy key positions, while other institutes complement ongoing research. Moreover, some institutes perform service functions for research performed at universities by providing equipment and facilities to a wide range of scientists, such as telescopes, large-scale equipment, specialized libraries, and documentary resources.

For more information, please click here

Contacts:
Max Planck Society
for the Advancement of Science
Press and Public Relations Department
Hofgartenstrasse 8
D-80539 Munich
Germany
PO Box 10 10 62
D-80084 Munich
Phone: +49-89-2108-1276
Fax: +49-89-2108-1207

Dr. Birgit Krummheuer, Press and Publicity Office
Max-Planck-Institute for Dynamics and Self-Organization, Göttingen
Tel.: +49 551 5176-668

Dr. Marc Timme
Max-Planck-Institute for Dynamics and Self-Organization, Göttingen
Tel.: +49 551 5176-440