Home > Press > A new kind of counting: Göttingenbased 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 SelfOrganization 
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 SelfOrganization 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öttingenbased 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 SelfOrganization (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öttingenbased 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 shortsighted, 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, largescale 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
D80539 Munich
Germany
PO Box 10 10 62
D80084 Munich
Phone: +498921081276
Fax: +498921081207
Dr. Birgit Krummheuer, Press and Publicity Office
MaxPlanckInstitute for Dynamics and SelfOrganization, Göttingen
Tel.: +49 551 5176668
Dr. Marc Timme
MaxPlanckInstitute for Dynamics and SelfOrganization, Göttingen
Tel.: +49 551 5176440
Copyright © Max Planck Society
If you have a comment, please
Contact us.
Issuers of news releases, not 7th Wave, Inc. or Nanotechnology Now, are solely responsible for the accuracy of the content.
Bookmark:
News and information
SEMATECH to Showcase Innovation and Advances in Manufacturing at SEMICON Japan 2014: SEMATECH experts will share the latest techniques, emerging trends and best practices in advanced manufacturing strategies and methodologies November 26th, 2014
Australian startup creates world’s first 100% cotton hydrophobic TShirts November 26th, 2014
The mysterious 'action at a distance' between liquid containers November 26th, 2014
'Giant' charge density disturbances discovered in nanomaterials: Juelich researchers amplify Friedel oscillations in thin metallic films November 26th, 2014
Discoveries
The mysterious 'action at a distance' between liquid containers November 26th, 2014
'Giant' charge density disturbances discovered in nanomaterials: Juelich researchers amplify Friedel oscillations in thin metallic films November 26th, 2014
Vegetable oil ingredient key to destroying gastric disease bacteria: In mice, therapeutic nanoparticles dampen H. pylori bacteria and inflammation that lead to ulcers and gastric cancer November 25th, 2014
Research yields material made of singleatom layers that snap together like Legos November 25th, 2014
Announcements
SEMATECH to Showcase Innovation and Advances in Manufacturing at SEMICON Japan 2014: SEMATECH experts will share the latest techniques, emerging trends and best practices in advanced manufacturing strategies and methodologies November 26th, 2014
Australian startup creates world’s first 100% cotton hydrophobic TShirts November 26th, 2014
The mysterious 'action at a distance' between liquid containers November 26th, 2014
'Giant' charge density disturbances discovered in nanomaterials: Juelich researchers amplify Friedel oscillations in thin metallic films November 26th, 2014