A research group based in Dresden, Vienna and Prague aims to shed new light on the theory of computational complexity with their collaborative project, “Polynomial-time Computation: Opening the Blackboxes in Constraint Problems,” or POCOCOP for short. The three researchers, Prof. Manuel Bodirsky (TU Dresden), Prof. Libor Barto (Prague) and Prof. Michael Pinsker (Vienna), have been awarded the European Research Council’s (ERC) prestigious Synergy Grant and a total funding amount of eight million euros in recognition of their work.

How can computational problems be grouped according to their difficulty? What problems can we solve with little time and effort? And what problems are impossible solve quickly and easily, no matter which methods we use? The question of how to distinguish between these two types of computational problems is one of the largest and most important problems of modern mathematics. With the POCOCOP research group, three researchers are joining forces to unravel these questions. Manuel Bodirsky, Chair of Algebra and Discrete Structures at TU Dresden, explains the project as follows: “The project systematically investigates which problems can be solved using an algorithm in polynomial time. In doing so, we want to make better use of powerful algorithm techniques that already exist, discover completely new algorithms, and also better understand what problems cannot be efficiently solved by computers.”

The starting point: P versus NP

The more elements you have, the longer it takes to solve a math problem. For example, if you have a list of numbers to sort, the job gets more complex as more numbers are added. However, the decisive factor is how quickly computational effort rises as the number of elements to be considered increases. If we increase the amount of numbers in a list, the computing time does not increase that dramatically. For example, we might consider sorting methods in which the time needed for sorting increases in proportion to the squared value of the total amount of numbers to be sorted. The computing time is therefore a polynomial (x² in this case) of the input size. In this example, we are talking about a problem in P.

However, there are also problems for which there is no known method for solving them in polynomial time. For example, imagine we have a certain number of people, some of whom do not like each other. The question is: Can these people be divided into three groups in such a way that there are no two people in any group who don't like each other?

The computing time needed to find this grouping increases not merely with a polynomial of the number of persons, but even faster – exponentially, in fact – if no better method is known. However, as soon as we have a solution, we do not need a lot of time to check if it is correct. Problems with this characteristic are known as NP.

The NP classification may seem a lot larger and more general than the P classification. The only given condition for a problem to be grouped as NP is that it must be possible to check the solution efficiently, whereas for a problem to fall into the P classification, the method for solving a problem itself must be quick and easy to find. But is there really a principally forever insurmountable difference between these two complexity classes? Or does an ingenious method for solving all NP problems in polynomial time exist that simply hasn’t been found yet? Hardly anyone believes this is possible in our day and age – but there is no conclusive proof to suggest it’s impossible either. The challenge of providing conclusive proof for this proposition is one of the famous Millennium Prize Problems of mathematics, which are endowed with one million dollars.

Fulfilling multiple requirements at once

The research team will take a closer look at constraint satisfaction problems – tasks whose applications are found all around us, from science to industry. They will investigate whether multiple requirements in a certain list can be fulfilled at the same time – for example, whether there are numbers with which a set of equations can be satisfied simultaneously. Or even whether a timetable can be made that matches the number of teaching staff in a school at any given time to the number of classes in the school, enabling a lesson to proceed in line with all the necessary rules. In practice, sometimes it is not necessary to meet all requirements at the same time. Perhaps you simply want to find a solution that at least fulfills as many of the requirements as possible – the POCOCOP project will also investigate these cases using complexity theory.

Manuel Bodirsky is looking forward to working with the team, stating, “This project constitutes an enormous boost for our field of research. Talented and motivated young researchers can now work on many of the exciting and promising research questions for which there simply was not enough time in the past. The collaboration between the three cities will be of particular value here because the three research groups’ concentrations complement each other well.”

“The general ERC Grants and the specialized Synergy Grants are among the world's most prestigious project grants for fundamental research. The researchers involved therefore leave behind a lasting impression in their field of research. For this reason, these grants represent a great success to the institutions involved. The Synergy Grants enable teams of excellent researchers to tackle problems that are virtually impossible to solve alone, without the collaborations that arise from the funding,” emphasize Rick Glöckner and Stefanie Kohl from TU Dresden’s European Project Center (EPC), which supported the three researchers’ project.

About ERC Synergy Grants:

The ERC Synergy Grants of the European Research Council (ERC) support teams of two to four individual researchers working at different locations. They provide funding for projects that lead to “progress at the frontiers of knowledge” via interdisciplinary collaboration. The grant is endowed with up to ten million euros over a period of six years. The POCOCOP project has been awarded almost 8 million euros in funding, of which 3.4 million euros have been allocated to TU Dresden, which is participating in an ERC Synergy Grant project for the first time.

More on Manuel Bodirsky:

Manuel Bodirsky was born in Freiburg im Breisgau in southwest Germany and studied Computer Science at Saarland University. He received his doctorate at Humboldt-Universität zu Berlin in 2004. From 2008 until his employment at TU Dresden in 2014, Manuel Bodirsky was Chargé de Recherche at the French Academy of Sciences. He is the Chair of Algebra and Discrete Structures at TU Dresden. From 2016 to 2021, he led an ERC Consolidator Grant on the mathematical foundations of constraint satisfaction problems.

Media inquiries:

Manuel Bodirsky
Chair of Algebra and Discrete Structures
TU Dresden
Email:
Tel: +49 351 463-35255