Tutorial: Current state of P vs NP problem

摘要

Do I understand the problem of P vs. NP? The answer is a simple "no". If I were to understand the problem, I would've solved it as well" — This is the current state of many theoretical computer scientists around the world. Apart from a bag of laureates waiting for the person who successfully understands this most popular millennium prize riddle, this is also considered to be a game changer in both mathematics and computer science. According to Scott Aaronson, "If P = NP, then the world would be a profoundly different place than we usually assume it to be". The speaker intends to share the part that he understood on the problem, and about the efforts that were recently put-forth in cracking the same.