Jannik Matuschke (TU Berlin)

2011/02/11, 12:45

Before the BMS Friday Colloquium by Prof. David Williamson

Before the BMS Friday Colloquium by Prof. David Williamson

Urania Berlin, at the BMS Loft (3rd floor)

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.