Lesson 3

For many problems in the class NP, we do not know whether an efficient algorithm can be constructed for them. This is the P vs NP problem, the so-called millennium problem, one of the main open problems in computer science and all of mathematics. The Clay Mathematics Institute has set a prize of one million dollars for its solution.