The Math Mystery That Connects Sudoku, Flight Schedules and Protein Folding
The Math Mystery That Connects Sudoku, Flight Schedules and Protein Folding
The Math Mystery That Connects Sudoku, Flight Schedules and Protein Folding
Jack Murtagh
January, 6, 2025
Summary
The P vs. NP problem in computer science revolves around whether problems whose solutions are easily verified (NP) can also be efficiently solved (P). NP-complete problems, such as Sudoku, the traveling salesperson problem, and protein folding, are at the heart of this mystery. A breakthrough in solving any NP-complete problem could solve them all due to their interconnected nature. This concept, introduced by Richard Karp, shows that solving one NP-complete problem could efficiently resolve a wide range of others. Whether these problems have efficient solutions remains unresolved, with implications for encryption, mathematics, and technology.
Reference
Murtagh, J. (2025, January 6). The math mystery that connects Sudoku, flight schedules, and protein folding. Scientific American. https://www.scientificamerican.com/article/the-math-mystery-that-connects-sudoku-flight-schedules-and-protein-folding/