Using chess and fractal geometry to better understand the structure of a particularly exotic type of crystal, British and Swiss physicists have devised an algorithm that has proven capable of producing a maze of absolutely fiendish complexity – the most difficult ever created, according to them.
The objects this team is working on are actually not quite crystals per se: they are actually quasicrystals. Unlike normal crystals, which are incredibly abundant, these quasicrystals are also exceptionally rare in the natural state. In fact, there are only a handful of known natural sources — and they are all meteorites.
Beyond their rarity, what makes these materials so interesting is their architecture. The atoms are arranged in a highly organized and symmetrical structure, like traditional crystals. But unlike the latter, atomic groups do not repeat periodically in space following a simple pattern. Instead, they exhibit much more elaborate types of symmetry.
« Quasicrystals have all these symmetries that could never exist in crystals, which is quite fascinating. It’s a very beautiful branch of mathematics — but anyone can appreciate the beauty of it directly, without needing to understand the details. ” explains Felix Flicker, co-author of the study quoted by New Scientist.
Crystal, Chess and Math
Since examples are not exactly flooding the door, science still has a lot to learn about the particularities of quasicrystals. In order to better understand these geometric aliens, the Flicker team decided to create an ultra-specialized algorithm to describe their structure. And to achieve this, they were inspired by… chess.
The lineage is not obvious, but the structure of quasicrystals does indeed present particularities with an old logic problem based on the movements of the most singular piece of the king of board games.
This puzzle, called Euler’s Knight, begins with a knight positioned on any square of the chessboard. The objective is to make it visit all the other squares without ever going through the same one twice. When we trace the path of this knight, we obtain what is called a Hamiltonian circuit, that is to say that it passes only once through all the points of a graph.
Now, it turns out that the structure of atoms in quasicrystals also follows this rule. And this is where this work gets interesting, because this similarity allows us to approach the problem from the perspective of complexity theory.
A foray into complexity theory
In general, finding a Hamiltonian circuit is what is called a NP-complete problem. This term refers to a problem whose complexity increases exponentially with the number of elements, to the point where it quickly becomes impossible to calculate the solution by brute force on our time scale. On the other hand, if we are faced with a potential solution, it is easy to quickly check whether it is valid, a bit like a puzzle where we only need to observe the final image.
The challenge is therefore to find a way to solve these so-called NP-complete problems in a reasonable time (or more precisely in a so-called polynomial time). And this is a problem that has been driving mathematicians crazy for decades. In fact, it even falls within the scope of P=NPone of the famous Millennium Prize Problems. This is a list of seven major mathematical problems whose solution comes with a million-dollar prize. So far, only one of them, the Poincaré Conjecture, has been solved (by Grigori Perelman in 2010).
This equation materializes an almost existential question for mathematicians: Are these complex problems really as difficult to tackle as they seem, or is there a simple general solution that no one has yet found to help you quickly find a solution?
If this P=NP hypothesis were to be confirmed one day, which is far from certain, the implications would be enormous. This would fundamentally change the nature of a host of problems that are very important to modern science, but today considered virtually insoluble (see our article below for more details).
The important point is that all specialists in complexity theory agree on one point: they consider that if there exists an algorithm to solve a single NP-complete problem in a reasonable (polynomial) time, then This means that there is also a relatively simple solution to ALL other NP-complete problemsincluding Hamiltonian circuits! And it turns out that many of them are exceptionally important to modern science. Examples include the traveling salesman problem, whose rapid resolution would immediately eliminate a bunch of extremely difficult logistical puzzles, or the protein folding mechanisms which the DeepMind teams tackled using machine learning.
Now, it turns out that Euler’s knight is a particular case. Although Hamiltonian circuits are generally NP-complete problems, there are a few that can be solved quickly with some mathematical sleight of hand. Euler’s knight is one of them: a solution can be found quickly with a simple method, the Warnsdorf algorithm. Since this problem is closely related to the structure of quasicrystals, the authors of this work therefore sought an analogous method to apply to their own problem.
And they found one, which allowed them to generate this incredibly difficult maze that illustrates the arrangement of atoms in these materials.
Not a proof of P=NP, but interesting concrete applications
According to researchers cited by ScienceAlertthis work could have very concrete implications in areas such as optics or carbon capture.
However, this does not mean that the Hamiltonian circuit problem has been solved once and for all; as with Euler’s Knight, it is simply a very elegant way of simplifying a very specific problem, and in no way a general solution.
By extension, it is also not an answer to the P=NP hypothesis and all the other NP-complete problems… but it may be a step in that direction. Who knows; if a rigorous solution ever emerges, this work may be remembered as one of the pieces that paved the way for one of the most important revolutions in the history of mathematics.
The text of the study is available here.
To not miss any news on the Journal du Geek, subscribe on Google News. And if you love us, we have a newsletter every morning.
