This is Jannik Matuschke's talk "What is ... P vs NP?" at the "What is ...?" seminar. The talk was given on Friday, February 11, 2011, 12:45pm at the BMS Loft at Urania.
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.
For more "What is ...?" seminar videos, visit math.fu-berlin.de/w/Math/WhatIsSeminar.