Noah here. A few years ago, I went deep into a physics and math rabbit hole. I can’t remember if it started with books or YouTube lectures, but what

The P vs. NP Edition

submited by
Style Pass
2022-01-12 20:30:10

Noah here. A few years ago, I went deep into a physics and math rabbit hole. I can’t remember if it started with books or YouTube lectures, but what began as an interest in understanding some scientific basics like E=mc^2, cascaded into reading about quantum mechanics and the Poincaré Conjecture. There was some real magic in trying to wrap my head around seemingly impossible concepts, and I came to appreciate (to whatever extent a layperson like myself can) how mind-bending it must be to work as a theoretical physicist or mathematician.

Over the last few weeks, I’ve been returning to the rabbit hole a bit as I make my way through the backlog of Caltech physicist Sean Carrol’s Mindscape podcast. Carrol turns out to be quite an adept interviewer, as he deeply understands the topics his guests are discussing but maintains both the curiosity and self-control to allow them to speak, only occasionally jumping in to clarify.

One recent episode I listened to was with theoretical computer scientist Scott Aaronson. I wrote about Aaronson a bit last year as quantum supremacy made the news, but for this conversation, he was more focused on a concept called complexity classes, and the computer science (CS)/math problem P vs. NP. P vs. NP is one of the great unsolved problems in cs/math and is one of the seven Clay Institute Millenium Problems with a million-dollar bounty. To get that million, all you have to do is prove that there’s a difference (or not) between problems that are easy for computers to solve (P) and those that are hard (NP). If that sounds a little crazy, it’s because it is. Nearly every person working on P vs. NP believes that P is not the same as NP—that there is some fundamental distinction between what is easy and hard for a computer to solve—but to this point, no one has proven this is true.

Leave a Comment