# What if P = NP? - Mathematician explains | Joel David Hamkins and Lex Fridman Source: https://www.youtube.com/watch?v=q6CReSu5mPk Recap page: https://rapidrecap.app/video/q6CReSu5mPk Generated: 2026-01-05T01:02:42.631+00:00 --- ## Quick Overview The discussion between Lex Fridman and Joel David Hamkins on the P vs NP problem concludes that while P=NP would lead to immense technological advancements by making previously intractable problems solvable efficiently, the consensus among computer scientists remains that P is not equal to NP, suggesting that finding solutions is generally harder than verifying them. **Key Points:** - The P vs NP problem asks if every problem whose solution can be quickly verified (NP) can also be quickly solved (P), with the essential question being: Is finding a solution as easy as checking one? - Joel David Hamkins notes that if P were equal to NP, it would lead to an 'immense wealth' for human civilization because all NP-complete problems, like the Boolean Satisfiability Problem (SAT), would become solvable in polynomial time. - SAT (Boolean Satisfiability) is cited as the first problem proven to be NP-complete, where SAT solvers efficiently find true/false assignments for complex Boolean formulas. - Hamkins suggests that while current SAT solvers work amazingly well for many practical cases, if P != NP, there will always be problems whose exponential nature prevents polynomial time solutions, even if approximations exist. - The discussion touches on the philosophical implications, noting that if P=NP, a statement's truth would be equivalent to its provability, which Hamkins finds counter-intuitive for logicians. - The general consensus among computer scientists, despite the theoretical possibility, is that P is not equal to NP (P ≠ NP). ![Screenshot at 00:09: A Venn diagram graphic clearly illustrating the relationship between NP-Hard, NP-Complete, NP, and P, with text defining P and NP and posing the core question: 'Is finding a solution as easy as checking one?'](https://ss.rapidrecap.app/screens/q6CReSu5mPk/00-00-09.jpg) **Context:** This segment is an excerpt from the Lex Fridman Podcast featuring mathematician Joel David Hamkins, focusing on one of the most significant unsolved problems in computer science and mathematics: the P versus NP problem. The conversation centers on defining P (problems easy to solve) and NP (problems easy to check), exploring the profound real-world consequences if P were proven equal to NP, and reviewing the current status and implications of this theoretical divide. ## Detailed Analysis Lex Fridman initiates a discussion with Joel David Hamkins about the P vs NP problem, which asks whether every problem whose solution is easy to verify (NP) is also easy to solve (P). Hamkins explains the definitions, noting P represents problems easy to solve, and NP represents problems easy to check once a solution is provided. Hamkins stresses the incredible impact if P=NP, suggesting it would unlock immense wealth and technological progress by allowing polynomial-time solutions for currently intractable NP problems, such as those encountered in engineering and science. He mentions the SAT problem (Boolean Satisfiability) as the first known NP-complete problem, noting that current SAT solvers work impressively well, often finding solutions quickly in practice. However, Hamkins emphasizes that even if approximations are available, if P is not equal to NP, there will always be problems whose exponential difficulty remains insurmountable within polynomial time, even for the most advanced algorithms. He touches on the philosophical aspect, noting that P=NP would imply that every mathematical truth is provable in polynomial time, a notion he finds counter-intuitive to the nature of logic and proof. The general scientific belief is strongly in favor of P ≠ NP. ### P vs NP Definition - P = Problems that are easy to solve - NP = Problems that are easy to check once a solution is provided - The essential question is: Is finding a solution as easy as checking one? ### Consequences of P=NP - Would lead to immense wealth for human civilization - All NP-complete problems would have feasible (polynomial time) algorithms - Solving engineering and scientific problems becomes easy. ### SAT Problem - SAT (Boolean Satisfiability) is the first problem proven NP-complete - SAT solvers work remarkably well for many practical cases, finding assignments that make a Boolean formula true. ### Implications of P≠NP - If P is not equal to NP, there will be inherently hard problems that will never have polynomial-time algorithms, even if approximations exist. ### Philosophical View - Hamkins notes that P=NP implying truth equals provability seems counter-intuitive to logicians, highlighting the theoretical depth of the question. ![Screenshot at 00:02: Lex Fridman visible in a small inset during the opening sequence with an animation of the Earth from space.](https://ss.rapidrecap.app/screens/q6CReSu5mPk/00-00-02.jpg) ![Screenshot at 00:09: A Venn diagram graphic clearly illustrating the relationship between NP-Hard, NP-Complete, NP, and P, with text defining P and NP and posing the core question: 'Is finding a solution as easy as checking one?'](https://ss.rapidrecap.app/screens/q6CReSu5mPk/00-00-09.jpg) ![Screenshot at 00:32: Guest Joel David Hamkins speaking into the microphone, dressed in a grey suit and bow tie.](https://ss.rapidrecap.app/screens/q6CReSu5mPk/00-00-32.jpg) ![Screenshot at 03:04: On-screen text defining SAT Solvers and SAT \(Boolean Satisfiability\) as the first proven NP-complete problem, with an example formula and solution.](https://ss.rapidrecap.app/screens/q6CReSu5mPk/00-03-04.jpg) ![Screenshot at 03:22: The closing screen showing the Lex Fridman Podcast logo and prompts to like and subscribe over an image of Earth from space.](https://ss.rapidrecap.app/screens/q6CReSu5mPk/00-03-22.jpg)