22
MENTIONS
3
EPISODES
3
PODCASTS
Search complete. 22 mentions across 3 episodes found for "NP".
Oct 12, 2026
Ryan PetermanHOST
You mentioned OpenAI sitting on proofs of major problems.
Ryan PetermanHOST
Let's say OpenAI was sitting on a proof to the Millennium Prize Problem of if P is equal to NP, and suppose they proved P was equal to NP.
Ryan PetermanHOST
How would that change the world?
Scott AaronsonGUEST
That would really change everything that we thought about computational complexity, right? That would, uh, that would sort of be a, a, a cataclysm for our universe, like even greater than the, the AI cataclysm, you could say, that is happening right now.
Scott AaronsonGUEST
It, it, it's also something, by the way, that could massively accelerate AI, okay? If, if, if the algorithm for solving NP problems were actually efficient in practice, which w- which would then be a further question, okay? But, uh, you know, my, my, my strong guess is that P is not equal to NP, right? [laughs] Um, you know, m- uh, I, I think that if, if and when that problem is solved, it is virtually certain at this point that AI will play a central role in the solution, right? The question is like will, will humans also play a role, right? That's...
Scott AaronsonGUEST
That, that, that's the, that's the question at this point.
Scott AaronsonGUEST
It's not like will AI be involved.
Scott AaronsonGUEST
It's like of course it will be.
Scott AaronsonGUEST
... those are still standing.
Scott AaronsonGUEST
Like, so, you know, the P versus NP problem, the Riemann hypothesis, you know, the Goldbach conjecture, you know, those have not been solved.
Scott AaronsonGUEST
But let's say, like, a level below that.
Scott AaronsonGUEST
You know, pri- I mean, problems that, you know, there were whole research communities, you know, that were ... you know, felt like they were closing in on them, you know, from various directions, right? And now they're just, boom, right? They're just the ...
46 MINS LATER
Joel BeasleyHOST
Wow.
Scott AaronsonGUEST
So, so, so it's like forget it.
Scott AaronsonGUEST
Okay, and so, so sort of the key question that we've been trying to answer since the, the 1960s or so is, like, of all the problems that you might wanna sol- solve with your computer, you know, we're just talking about well-defined mathematical problems, you know, for now, like, which ones have an algorithm with polynomial scaling, and which ones require exponential scaling? Okay? And so the most famous problem in, uh, uh, complexity theory is called the P versus NP problem, right? That, that's one of these Clay Millennium Problems, right? It's one that, you know, uh, OpenAI and Anthropic are now racing to solve with their, you know, very powerful internal models, but have not yet solved.
Scott AaronsonGUEST
Uh, uh, okay? And, uh, um, a- and, and, and it basically asks, uh, uh, whenever there is a polynomial algorithm, you know, which is sort of our rough and ready criterion for a fast algorithm, right? Whenever there's sort of a fast algorithm to recognize the solution to a problem, then is there also a fast algorithm to find the solution?
Andy BoydHOST
Then, they'll continue building the mathematical orange pile while waiting for someone to come up with a proof.
Andy BoydHOST
Of course, there has to be good reason to take this exceptional step, and that's the case for the famous P versus NP conjecture.
Andy BoydHOST
The conjecture impacts all sorts of practical problems.
Andy BoydHOST
Internet security, truck dispatching, circuit board design.
Andy BoydHOST
These are just a few of the problems that belong to a class called NP.
Andy BoydHOST
Some of the problems in NP are known to be easy.
Andy BoydHOST
That is, we can solve them pretty quickly.
Andy BoydHOST
This subclass of easy problems is called P.