# The greatest unsolved problem in computer science... Source: https://www.youtube.com/watch?v=x36UmiSiEzc Recap page: https://rapidrecap.app/video/x36UmiSiEzc Generated: 2026-03-09T19:01:47.801+00:00 --- ## Quick Overview The P versus NP problem, which asks if every problem whose solution can be quickly verified can also be quickly solved, remains unsolved despite decades of research, with the overwhelming consensus among complexity theorists leaning towards P being unequal to NP (P ≠ NP), a conclusion supported by the intractable nature of known NP-Complete problems like the Traveling Salesman Problem and SAT. **Key Points:** - The P vs NP problem asks if P (problems solvable quickly) equals NP (problems verifiable quickly), and it is one of the seven Millennium Prize Problems with a $1 million reward. - The overwhelming consensus among complexity theorists is that P does not equal NP (P ≠ NP), as evidenced by polls showing 88% of respondents believing P ≠ NP in 2019. - Problems in NP, like the Traveling Salesman Problem (TSP), are easy to verify (check if a given route is short) but hard to solve (find the optimal route, which is factorial complexity, O(N!)). - NP-Complete problems, such as SAT (Boolean Satisfiability Problem), TSP, and Graph Coloring, are the hardest problems in NP; solving one efficiently (in P time) would imply all NP problems are solvable in P time. - Early research by Stephen Cook in 1971 established the NP-Completeness of SAT by showing it could polynomially reduce other problems to it. - Modern encryption methods like RSA rely on the presumed difficulty of factoring large numbers (a problem believed to be outside P, or at least significantly harder than verification), which would be broken if P=NP. - Current proof techniques, such as Relativization, Natural Proofs, and Algebraization, have all hit barriers in attempting to prove P vs NP. ![Screenshot at 0:01: A visual comparison pitting a single green pea \(representing P\) against a green pea marked with the letter 'n' \(representing NP\) to introduce the central question of the video: P vs NP.](https://ss.rapidrecap.app/screens/x36UmiSiEzc/00-00-01.jpg) **Context:** The video explains the P versus NP problem, a central unsolved question in computer science and mathematics concerning the relationship between problems that are easy to solve (P) and problems whose solutions are easy to verify (NP). The discussion details the implications of P=NP, contrasting the computational complexity of problems like sorting (O(N^2)) and factoring large numbers (the basis of RSA encryption) against the ease of verification. ## Detailed Analysis The video explores the P vs NP problem, one of the seven Millennium Prize Problems offering a $1 million reward for a solution. The core question is whether every problem whose solution can be verified quickly (in polynomial time, P) can also be solved quickly (in polynomial time, NP). Currently, the consensus among complexity theorists strongly suggests P ≠ NP, with polls showing 88% belief in P ≠ NP as of 2019. The difficulty stems from problems where verification is easy but finding the solution is hard, like the Traveling Salesman Problem, which has factorial complexity (O(N!)) for brute force search, or factoring large numbers, which underpins RSA encryption security. The video illustrates that if P=NP, then all NP-Complete problems—like SAT, TSP, and Graph Coloring—could be solved efficiently, leading to chaotic implications across fields, including breaking modern cryptography and making previously impossible tasks trivial. It highlights Stephen Cook's 1971 paper proving SAT is NP-Complete via polynomial reduction. The video concludes by showing that attempts to prove P vs NP have been blocked by known theoretical barriers, including Relativization, Natural Proofs, and Algebraization, suggesting that proving P ≠ NP will require entirely new mathematical tools. ### Introduction to P vs NP - P represents problems solvable in polynomial time (e.g., sorting in O(N^2)); NP represents problems verifiable in polynomial time (hard to solve, easy to check). - The consensus strongly favors P ≠ NP, with 88% of theorists agreeing as of 2019. ### Complexity Examples - Bubble Sort is O(N^2), which is polynomial time (P). - Factoring large numbers (RSA) is believed to be hard (NP), as finding the prime factors P and Q from N is exponentially harder than multiplication P*Q=N. ### NP-Complete Problems - These are the hardest problems in NP; if one is solved in P time, all NP problems fall into P. - Examples shown include SAT (Boolean Satisfiability Problem, Cook's 1971 proof), Traveling Salesman Problem (TSP), Sudoku, and Graph Coloring. ### Implications of P=NP - If P=NP, the world changes overnight; currently hard problems (like breaking RSA encryption or solving complex scheduling) become trivial, leading to potential chaos (e.g., cracking all public-key cryptography). ### Proof Barriers - Mathematicians have tried various methods to prove P vs NP, including Relativization [R], Natural Proofs [N], and Algebraization [A], but all have encountered barriers, suggesting a new approach is needed. ![Screenshot at 0:08: Screenshot of the Clay Mathematics Institute website explaining the P vs NP problem and the associated $1,000,000 prize.](https://ss.rapidrecap.app/screens/x36UmiSiEzc/00-00-08.jpg) ![Screenshot at 0:59: A diagram illustrating the complexity hierarchy, showing P contained within NP, and NP-Complete problems sitting outside P but within NP \(under the assumption P ≠ NP\).](https://ss.rapidrecap.app/screens/x36UmiSiEzc/00-00-59.jpg) ![Screenshot at 2:13: Visual examples of NP problems: the Traveling Salesman Problem \(a complex route map\) and a Sudoku puzzle, illustrating problems that are easy to check but hard to solve.](https://ss.rapidrecap.app/screens/x36UmiSiEzc/00-02-13.jpg) ![Screenshot at 4:45: A collage of various NP-Complete problems, including SAT, TSP, Knapsack, and Graph Coloring, overlaid on Stephen Cook's 1971 paper.](https://ss.rapidrecap.app/screens/x36UmiSiEzc/00-04-45.jpg)