Focus points for the Complexity Theory group

Complexity Theory from the underground

In the basement of the Turing Building sits a group of people who are working on Complexity Theory. From a place just under the surface of the Earth they tackle some of the most fundamental problems of theoretical computer science.

 “I believe that if we were at an American university we would be called “the Theory Group”, says Peter Bro Miltersen, Professor and leader of the Department of Computer Science’s Complexity Theory group. Together with the two post docs Maurice Jansen, Kristoffer Arnsfelt Hansen and academic researcher Gudmund Frandsen he works on creating a theoretical basis for evaluating which solution methods should be focused on. Peter Bro Miltersen states:
 “Complexity Theory is all about which types of algorithms are able to solve which problems. People believe that this is all very theoretical, but in reality it is incredibly practical. The most important thing is that the theory can be used to eliminate the types of algorithms that cannot be used. You are blind when attempting to navigate through a room of possible solution methods if you are not familiar with this theory.

A one million dollar question
To mark the entry into the new millennium in 2000, The Clay Mathematics Institute of Cambridge in Massachusetts, USA, set out seven mathematical problems, known as The Millennium Problems, and offered a prize of 1,000,000 Dollars for the correct solution to each of the problems.
One of the problems is quite simply expressed as P=NP? This expresses the fundamental problem with which Complexity Theory concerns itself.  Peter Bro Miltersen explains:
 “If P is equal to NP, this means that for each problem that could be solved by means of an exhaustive search, there is a much more effective method than this exhaustive search, namely a method that uses time that is not exponentially increasing with the size of the specific problem.  

Complexity Theory in practice
As anybody who has attempted to find a needle in a haystack will know, there are problems that appear to only be solvable through a thorough search.  This is why the majority of researchers believe that P is not equal to NP. Certain concrete problems are termed as being “NP-hard”. These problems could only be solved in sub-exponential time if this was possible for all problems in NP and it is here that the Complexity Theory can be used practically:
“If you know your Complexity Theory, it would not take long to evaluate whether a solution method, for example one based on linear programming could be used at all. If the problem can be categorised as NP-hard, you should not waste more time using such a method, unless of course P is equal to NP and as I have already stated, we do not believe this to be the case”, says Peter Bro Miltersen.
The fact that the problem is NP-hard does not mean that you need to give up. It just means that some other types of algorithms should be used that can bring you a sufficiently good solution.

From algebraicists to cryptologists
The Complexity Theory group works in close collaboration with other groups including the Game Theory group, with which it overlaps on a personal and thematic level. However, they also work together with a broad spectrum of people and disciplines from algebraicists to cryptologists.
The group is financed through a combination of faculty funds and funds from the Danish Natural Science Research Council and the Carlsberg Foundation.