FINDING VS. VERIFYING

Content

For many problems we can find solutions quickly with help of computers. This class of problems is called P. But there are also a large number of problems, where even the fastest computers are not able to solve them. A special class is NP: for these problems we are able to verify whether a solution is correct, but we are not able to find new solutions efficiently.

Even after 40 years the question remains whether for all problems in NP also solutions can be found efficiently, in other words: P equals NP. This question is one of the millennium problems of the Clay Mathematics Institute. We look at the question whether P equals NP, have a look at why many researchers do not believe that P equals NP and we look at possible consequences of P equals NP and P is unequal to NP.

General information

This course will take place in the fourth quartile of your first year. It will be given by Bodo Manthey.

Teachers

Bodo Manthey

Bodo Manthey

Bodo Manthey earned his PhD in computer science from the University of

Lübeck. After postdoctoral positions at Saarland University and Yale

University, he joined the Department of Applied Mathematics at the

University of Twente in 2009 as an Assistant Professor.

 

 

Back to programme