Episode 100: Unsolved Problems in Science

NP Problems

James Fodor introduces the concept of NP problems, emphasizing their significance in computer science. He explains that NP problems are those where solutions can be verified quickly, even if finding the solution is difficult. For instance, integer factorization is an NP problem because, while multiplying two numbers is straightforward, verifying the solution is relatively easy 1. James highlights the ongoing debate about whether P equals NP, a question that remains unsolved. He notes, "Most computer scientists and mathematicians, as far as I can tell, think that P does not equal NP. But again, no one's been able to prove that" 2.

   

Complexity Classes

James delves into complexity classes, focusing on P and NP, which categorize problems based on their difficulty. P represents problems solvable in polynomial time, while NP includes problems verifiable in polynomial time but not necessarily solvable quickly 3. He further explains NP-complete problems, the hardest within NP, which can be reduced to solve any other NP problem. Examples include Boolean satisfiability and the traveling salesman problem 4. James clarifies, "If you can solve any one problem that's NP complete, you can actually solve all of the other problems in NP" 4.

   

Intermediate & Cryptography

The discussion moves to NP intermediate problems, which are neither NP-complete nor in P, highlighting their elusive nature. James mentions integer factorization as a suspected NP intermediate problem, lacking a polynomial time solution yet not proven NP-complete 5. He also explores the implications of the P vs NP problem on cryptography, particularly RSA cryptography, which relies on the difficulty of factorizing large integers 6. He states, "Public key cryptography relies on the fact that some things are easy to check but hard to solve" 6.