23 August 2011

Unsolved computer science riddle faces serious challenges

COLA, the lifespring of any computer scientist, is now also the name of an ambitious research project aiming at solving a million dollar question of computer science.

Associate professor at DIKU Jakob Grue Simonsen has received a 1m Euro Grant from the Danish Sapere Aude program for young research managers, governed by the Danish Council for Free Research for the funding of a research project aiming at solving one of the fundamental questions of computer science over the next four years, including "Can it be proved that P = NP or not? Or - in other words - why can't any complex problem simply be solved by an appropriate algorithm and a supercomputer".

COLA stands for Complexity via Logic and Algebra and is a pure basic research project. With the efforts of leading international researchers within logic, mathematics and computer science COLA will investigate and hopefully develop new theoretical approaches to one of the most essential unsolved problems of algorithmics and computability. The main objective is not necessarily to find a final solution, but to develop new mathematical tools that may be of use in getting closer to solving these problems.

A dream come true: Solving a major riddle of the universe

"It is one of my boyhood dreams now finally coming true", says Jakob Grue Simonsen. "The large open questions have always fascinated me. Is it at all possible to attack som of the problems that have puzzled my research fellows for more than 40 years? At least we will try."

With a team of two post-docs, two phd students and a number of leading international guest researchers the COLA project will investigate new approaches to solving the problem which in mathematical terms is referred to as the P versus NP problem. P stands for a class of problems with "effective" solutions whereas NP stands for a class of problems whose solution can be substantiated fairly easy. But noone has ever succeeded in making these ends meet simply by programming or creating an algorithm.

The P = NP problem has puzzled researchers to an extent that is has been declared one of seven millenium riddles of research. The Massachusetts Clay Mathematics Institute has put a prize of 1 million dollars to he or she who can solve the P vs. NP problem.

The COLA-team will be established at the Southern Campus of the University of Copenhagen. The Sapere Aude-grant runs from April 2012 to March 2016.

Further information: simonsen@diku.dk or tel.  35 32 14 39

Read the KU press release about all Sapere Aude-grants to KU in 2011 (in Danish).

Read the press release from the Danish Research and Innovation Board about the 250 mio. DKK to 33 grant receivers (in Danish).