P vs NP

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.

Share

6 thoughts on “P vs NP”

  1. What’s up colleagues, how is everything, and what you desire to
    say regarding this article, in my view its genuinely remarkable in favor of me.

    1. Valuable info. Lucky me I found your web site by chance, and
      I’m shocked why this coincidence didn’t happened earlier!
      I bookmarked it.

  2. When I initially commented I clicked the “Notify me when new comments are added”
    checkbox and now each time a comment is added I get several
    e-mails with the same comment. Is there any way you can remove people
    from that service? Thank you!

  3. 独りの引っ越しなら赤帽がいいです。私が単独の引っ越しをするときに頻繁に活用します。赤帽は配達の感覚があると思いますが引越しも行っています。荷物が少ない引越しなら割安の業者です。個人事業のため連絡にこまる時にはネット見積もりを活用して見積もりするいいと思います。大変いいですよ。

  4. サラリーマンがアーリーリタイヤするには、毎月の暮らしをまかなう収入源が必要です。働かずしてマネーを作り出すには資産を手に入れるしかありません。そのための選択肢の一つが不動産投資です。お金のなる木である不動産という資産を購入することで、早期退職も可能となるのです。ただ不動産投資といってもアパート一棟の場合もあれば区分マンションの場合もあり、さまざまなスタイルがあります。またレバレッジをどのように利用するのかという点もあるので、自分にはどのようなスタイルが合っているのかを見極めながら投資活動を進めることが重要です。

Leave a Reply

Your email address will not be published.