Key Moments
The greatest unsolved problem in computer science...
FireshipKey Moments
P vs NP: Can problems solvable quickly also be found quickly? Unsolved CS mystery with $1M prize.
Key Insights
The P vs NP problem questions whether problems verifiable in polynomial time can also be solved in polynomial time.
If P=NP, every password and encryption key would be instantly crackable, leading to widespread chaos.
Conversely, P=NP could also enable solutions to complex problems like curing cancer or ending world hunger.
The problem was formally defined by Stephen Cook in 1971, but its roots trace back much further.
NP-complete problems are the hardest in NP; if one is solved efficiently, all NP problems are solvable efficiently.
Mathematicians have struggled for decades to prove or disprove P vs NP, facing significant theoretical barriers.
THE HIGH-STAKES NATURE OF P VS NP
The P vs NP problem stands as one of computer science's most significant unsolved challenges, with the Clay Mathematics Institute offering a $1 million prize for its solution. At its core, the problem probes whether problems whose solutions can be quickly verified can also be quickly solved. While many intuitively believe P does not equal NP, a definitive proof remains elusive, highlighting the profound implications for cryptography, security, and problem-solving.
HISTORICAL ROOTS AND FORMULATION
The P vs NP problem's official definition emerged in 1971 with Steven Cook's work on theorem proving complexity. However, its conceptual underpinnings can be traced back to 1955, when mathematician John Nash alerted the NSA to the exponential increase in effort required to break codes as key lengths grow. Nash's warning implicitly suggested that code-breaking, a verification task, was not as easily or quickly solvable as its verification, hinting at P not equaling NP.
DEFINING CLASS P: POLYNOMIAL TIME
Class P encompasses problems that computers can solve efficiently, meaning the time required to find a solution grows at a polynomial rate relative to the input size. An example is sorting a list of names; as the list doubles, the computation time increases reasonably, typically by a factor of n or n log n. Such problems are deterministic and scale predictably, making them tractable for computers.
UNDERSTANDING CLASS NP: NON-DETERMINISTIC POLYNOMIAL TIME
Class NP includes problems where a proposed solution can be verified quickly (in polynomial time), but finding that solution from scratch can be computationally infeasible. Classic examples include the Traveling Salesman Problem, Sudoku, and complex scheduling tasks. While checking a given route's validity or a Sudoku's correctness is fast, discovering the optimal route or solving the puzzle itself can require immense computational power.
THE CHALLENGE OF PRIME FACTORIZATION
Prime factorization serves as a clear illustration of the P vs NP distinction. Multiplying two large prime numbers is a facile task for a computer, falling into class P. However, given a very large composite number, the process of finding its prime factors is exceedingly difficult and time-consuming, representing an NP problem. This asymmetry underpins modern public-key cryptography, like RSA encryption, due to the ease of encryption and the extreme difficulty of decryption without the key.
NP-COMPLETE PROBLEMS: THE HARDEST OF THE HARD
NP-complete problems represent the most challenging within the NP class. If a polynomial-time solution can be found for any single NP-complete problem, then all problems in NP can be solved efficiently. The Boolean satisfiability problem (SAT) was the first problem proven to be NP-complete. Many other critical problems, such as the Traveling Salesman Problem and protein folding, have since been shown to be NP-complete.
THE IMPLICATIONS IF P EQUALS NP
Should it ever be proven that P equals NP, the consequences would be revolutionary and potentially chaotic. All problems currently considered computationally intractable, including breaking most modern encryption, would become easily solvable. On the flip side, this would enable rapid solutions to previously insurmountable challenges, potentially leading to breakthroughs in medicine, artificial intelligence, and complex optimization tasks.
PROVING OR DISPROVING P VS NP: ONGOING STRUGGLES
Despite decades of intense research and numerous attempts by mathematicians, a conclusive proof for or against P vs NP remains elusive. Various proof methodologies have been explored, but each has encountered significant theoretical hurdles. The difficulty lies in proving the non-existence of efficient algorithms for problems where verification is easy but finding is hard, or vice-versa.
PHILOSOPHICAL AND EXISTENTIAL CONSIDERATIONS
The P vs NP problem transcends pure computer science, touching upon fundamental questions about the nature of reality and efficiency. If P=NP, it suggests a universe that is fundamentally efficient, where every puzzle has a shortcut. If P!=NP, it implies inherent computational limits, potentially hinting at a simulated reality designed to conserve processing power. Some even speculate that humanity's existence could be the very algorithm designed to compute the answer.
Mentioned in This Episode
●Software & Apps
●Organizations
●Books
●Concepts
●People Referenced
Common Questions
P versus NP is computer science's biggest unsolved problem, asking if problems whose solutions can be verified quickly (NP) can also be solved quickly (P). Proving it could offer immense benefits or catastrophic security risks.
Topics
Mentioned in this video
An example of an NP problem where finding the shortest route to visit multiple cities is difficult, but verifying a given route's length is easy.
A problem in biology and computer science that is NP-complete, highlighting the broad applicability of these complex computational challenges.
The class of problems (NP) where solutions can be verified quickly, but finding the solution might take an infeasibly long time.
The class of problems (P) that a computer can solve efficiently, with computation time growing at a reasonable, deterministic pace relative to input size.
The most famous unsolved problem in computer science, questioning if problems whose solutions can be quickly verified can also be quickly solved.
A puzzle used as an example of an NP problem, where verifying a solution is easy, but finding it from scratch can be hard.
More from Fireship
View all 16 summaries
6 minCloudflare just slop forked Next.js…
7 minWhen open-sourcing your code goes wrong...
3 minTanStack Start in 100 Seconds
6 minHow AI is breaking the SaaS business model...
Found this useful? Build your knowledge library
Get AI-powered summaries of any YouTube video, podcast, or article in seconds. Save them to your personal pods and access them anytime.
Get Started Free