A new way of classifying algorithmic problems in algebra

A finite set of instructions that define how to manipulate or compute certain data is known as an algorithm, and it is through algorithms that we learn fundamental algebraic operations like the addition and multiplication of natural numbers. Since antiquity, mathematicians have been drawn to the connections between computation and algebra. In 1911, Max Dehn posed three fundamental problems that naturally arise in algebra (the isomorphism problem, the word problem, and the conjugacy problem) and he asked whether such problems could be solved by algorithmic means. It turns out that Dehn`s problems are generally unsolvable, meaning that no computer will ever be able to settle them: this is one of the most spectacular applications of logic to general mathematics. The main scientific goal of this project is to introduce and explore a new way of measuring the complexity of the principal algorithmic problems appearing in algebra. We will use cutting-edge methods from the theory of equivalence relations, which enable to calibrate the complexity of algorithmic problems in a very precise way. More generally, we will combine ideas and techniques from a wide range of mathematical fields, such as computability theory, universal algebra, or group theory, thus promoting collaboration between different mathematical communities. In a nutshell, we aim to have an impact at the interface between the theory of computation and algebra, by expanding theoretical knowledge of which algebraic issues are algorithmically tractable and which are not.

A finite set of instructions that define how to manipulate or compute certain data is known as an algorithm, and it is through algorithms that we learn fundamental algebraic operations like the addition and multiplication of natural numbers. Since antiquity, mathematicians have been drawn to the connections between computation and algebra. In 1911, Max Dehn posed three fundamental problems that naturally arise in algebra (the isomorphism problem, the word problem, and the conjugacy problem) and he asked whether such problems could be solved by algorithmic means. It turns out that Dehn's problems are generally unsolvable, meaning that no computer will ever be able to settle them: this is one of the most spectacular applications of logic to general mathematics. The main scientific output of this project has been the systematic exploration of a new way of measuring the complexity of the principal algorithmic problems appearing in algebra. We used cutting-edge methods from the theory of equivalence relations, which enable to calibrate the complexity of algorithmic problems in a very precise way. More generally, we combined ideas and techniques from a wide range of mathematical fields, such as computability theory, universal algebra, or group theory, thus promoting collaboration between different mathematical communities.