Recently a video purporting to explain the P vs. NP problem to the layman was on the front page of Reddit. This problem is really fun to think about, and the fact that it seemingly has something very fundamental to say about the nature of reality is striking. Here we have a problem whose formulation was motivated by the invention of glorified adding machines that is expressed in the language of highly abstract mathematics, BUT its resolution (in either direction) will indisputably inform our views about the nature of nature. I’m not much of a Platonist but this sort of profound connection between mathematics and reality is always very intriguing. I’m much more comfortable with the unreasonable effectiveness of mathematics when it comes to mathematics being able to accurately model the physical world. This has never really been a sticking point in my mind, it seems to me that if nature behaves in a predictable way (“predictable” here meaning that identical systems will reliably produce self-consistent, sensible outcomes), then something like mathematics must be able to faithfully represent it. However what the resolution of P vs. NP will mean for our understanding of the universe seems in some sense deeper. Or maybe not. Maybe mathematics being able to predict the position of a moving object 1 second into the future is just as spooky as P vs. NP telling us about the limits of information processing in the universe. I’m really not sure.
Here’s my “elevator speech” version of the problem taken from some of my old notes:
Solutions for problems in the class P can be found efficiently in polynomial time. Trivially this means that candidate solutions to problems in P can be checked in polynomial time (by just using the efficient algorithm to find the solution and checking if it matches the candidate solution).
Given a candidate solution, you can verify it in polynomial time for problems in NP. This class therefore includes P, and the crux of the P vs. NP problem is whether or not being able to verify a solution in polynomial time implies a solution can be found in polynomial time in the first place.
So-called NP complete problems are in the category NP, but an efficient solution for any NP complete problem could be applied to any NP problem (in polynomial time). Interestingly all known problems which are in NP but not in P are NP complete. The existence of a problem which is in NP (and not in P) but not NP complete would actually show that P ≠ NP.
NP hard problems include all NP complete problems, but they also include all other decision problems where a candidate solution cannot be verified in polynomial time. If P = NP then all NP problems are NP complete and P = NP, so all decision problems would fall into the NP hard class. If P ≠ NP then problems in P and problems in NP which are not NP complete would not fall into the NP hard class.
There are lots of other complexity classes, but these are the most important ones.
For more on this topic and the implications of the ability to solve NP complete problems efficiently would have on our understanding of reality, I recommend reading NP-complete Problems and Physical Reality by Scott Aaronson, who was quoted in the video linked at the start of this post.
As a closing thought I’d like to point out the fact that these sorts of videos which explain interesting problems in math are able to gain so much traction with the general public. This speaks to how fascinating the subject can be even for “non-math people.” The stigma against math (and indeed wearing ones distaste for math as a sort of hip badge of honor) speaks to a collective failure to teach math the right way. Paul Lockhart discusses this issue in great detail in his excellent essay A Mathematician’s Lament which I highly recommend reading. I don’t agree with everything he says, but nevertheless I think he raises many valid points. Ever since reading this essay I am reminded of it every time I see lots of people excited about math videos such as this or (less encouragingly) when I see students frustrated with stupid homework problems.