NP Intermediate Problems
The discussion delves into the concept of NP intermediate problems, which sit between easy (P) and hard (NP complete) problems. Integer factorization and graph isomorphism are highlighted as suspected NP intermediate problems, though their classifications remain unproven. The crux of the P vs NP hypothesis suggests that if problems can be easily verified, they may also be easily solvable, challenging our intuitive understanding of complexity in problem-solving.In this clip
From this podcast
The Science of Everything Podcast
Episode 100: Unsolved Problems in Science
Related Questions