P v NP

Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question “are there problems for which the answers can be checked by computers, but not found in a reasonable time?” If the answer to that is yes, then P does not equal NP. However, if all answers can be found easily as well as checked, if only we knew how, then P equals NP. The area has intrigued mathematicians and computer scientists since Alan Turing, in 1936, found that it’s impossible to decide in general whether an algorithm will run forever on some problems. Resting on P versus NP is the security of all online transactions which are currently encrypted: if it transpires that P=NP, if answers could be found as easily as checked, computers could crack passwords in moments.

→ Listen on BBC Sounds website

Guests

• Colva Roney-Dougal 11 episodes
  Reader in Pure Mathematics at the University of St Andrews
• Timothy Gowers 4 episodes
  Royal Society Research Professor in Mathematics at the University of Cambridge
• Leslie Ann Goldberg 2 episodes
  Professor of Computer Science and Fellow of St Edmund Hall, University of Oxford

Reading list

• Quantum Computing Since Democritus
  Scott Aaronson (Cambridge University Press, 2013) Google Books →
• In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
  William J. Cook (Princeton University Press, 2012) Google Books →
• The Golden Ticket: P, NP, and the Search for the Impossible
  Lance Fortnow (Princeton University Press, 2013) Google Books →
• Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists
  Dennis Shasha (Springer, 2008) Google Books →

Related episodes

• The Poincaré Conjecture
  
  2 Nov, 2006 510 Mathematics
• Mathematics’ Unintended Consequences
  
  11 Feb, 2010 510 Mathematics
• Fermat’s Last Theorem
  
  25 Oct, 2012 510 Mathematics
• Godel’s Incompleteness Theorems
  
  9 Oct, 2008 510 Mathematics
• Prime Numbers
  
  12 Jan, 2006 510 Mathematics
• Random and Pseudorandom
  
  13 Jan, 2011 510 Mathematics
• Alan Turing
  
  15 Oct, 2020 510 Mathematics
• Artificial Intelligence
  
  8 Dec, 2005 000 Computer science, knowledge and systems
• Theories of Everything
  
  25 Mar, 2004 530 Physics
• Consciousness
  
  25 Nov, 1999 120 Epistemology

Experimental. For more related episodes, visit the visual explorer.

---

Programme ID: b06mtms8

Episode page: bbc.co.uk/programmes/b06mtms8

Auto-category: 510 (Mathematics)