$\vec{w}h\alpha\mathfrak{t}\;\; i\mathbb{S}\ldots$

P vs. NP?

Jannik Matuschke (TU Berlin)
Urania Berlin, at the BMS Loft (3rd floor)
About what?

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.