Hardness of Approximation Between P and NP
991 views · Published 2 December 2016 · 49:50 · Indexed 12 November 2026
Channel: Microsoft Research · 2016 · Science & Technology
The first question we computer scientists ask when facing a new algorithmic challenge is: is it NP-hard, or is it in P? Surprisingly, for many important problems, the answer is "neither!" I will discuss recent progress towards understanding the complexity of those problems. See more on this video at https://www.microsoft.com/en-us/research/video/hardness-approximation-p-np/