Computer scientists to work on Millennium Problem

How would you plan your route if you had to visit all your favourite Copenhagen spots in as little time as possible? At the Department of Computer Sciences (DIKU), the newly established Cola group will work on similar problems.

»Cola stands for COmplexity through Logic and Algebra. Complexity theory is the branch of computer science that considers how efficiently we can solve problems,« says the head of the group, Associate Professor Jakob Grue Simonsen.

He defines himself as a computer scientist that sometimes works very much as a mathematician, and who usually works with mathematicians. Besides his PhD, he also got an MBA to be sure he could have a career even outside of science.

Cola will work on a Millennium Problem

The Cola group will study if efficient methods can be used to solve problems like the ‘travelling salesman’ one. In this problem, given a list of cities and the distances between them, the task is to find a shortest possible tour that visits each city once. The Cola group will help finding out whether the problem can be solved in a reasonable amount of time, if it can’t be solved, or if it is simply impossible to say if it can or not.

Among mathematicians, the class of problems that will be studied by Simonsen is summarized with the question “is P=NP?”. This has been classified as one of the Millennium Problems by the Clay Mathematics Institute, and its solution will be awarded with one million dollars. P and NP are two classes of problems, and “P=NP?” is the question of whether these two classes are equal. » Indeed, it is the million dollar question« Simonsen comments.

Math to get rid of math

»This is my favorite issue where resolution of the P=NP? problem would have a serious impact: Is it possible to use a computer to prove if a certain kind of mathematical conjecture has a proof, or not, in a reasonable amount of time?« Simonsen asks.

»In my opinion, mathematics should help people with non-creativity. To put their creativity to other matters instead of solving problems. This would save a lot of time and also a lot of thinking,« he adds.

The Cola research group will collaborate with computer science research groups in Oslo, Tel Aviv and Innsbruck. »Our focus and goal is not to crack the million dollar problem. Our ambition and purpose is to develop math that may, in the future, help us, or other researchers crack the Millennium Problem.« Simonsen finishes off.

Check the press release from DIKU here.

uni-avis@adm.ku.dk

Stay in the know about news and events happening in Copenhagen by signing up for the University Post’s weekly newsletter here.