What is … P vs NP?

This page hosts information on Jannik Matuschke's talk "What is … P vs NP?" at the "What is …?" seminar. The talk will take place on Friday, February 11, 12:45pm at the BMS Loft at Urania. This talk will help you better understand the talk by David Williamson, which will start at 2pm.

We will again be ordering delivery pizza. If you would like to order pizza with us, please arrive to the "What is …?" seminar by 12:30.

Abstract

Complexity theory is a branch of theoretical computer science that deals with the limits of efficient computability. Complexity classes allow us to compare the computational hardness of problems from a theoretical point of view. We will give formal definitions of the classes P ("problems that can be solved efficiently by a deterministic computer as we all know it") and NP ("problems that can be solved efficiently by a non-deterministic computer that can guess the answer and only needs to verify its correctness") and motivate the importance of the great open question whether or not P = NP.

Video

The video for Jannik's talk can be found at http://www.vimeo.com/23633895.

Comments