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.

With

Colva Roney-Dougal
Reader in Pure Mathematics at the University of St Andrews

Timothy Gowers
Royal Society Research Professor in Mathematics at the University of Cambridge

And

Leslie Ann Goldberg
Professor of Computer Science and Fellow of St Edmund Hall, University of Oxford

Producer: Simon Tillotson.

Release date:

Available now

43 minutes

Last on

Thu 5 Nov 2015 21:30

Related topics

LINKS AND FURTHER READING

Colva Roney-Dougal at the University of St Andrews

Timothy Gowers at the University of Cambridge

Leslie Ann Goldberg at the University of Oxford

P versus NP problem - Wikipedia

P vs. NP for Dummies

Gödel’s Lost Letter and P=NP

MacTutor History of Mathematics archive

 

READING LIST:

Scott Aaronson, Quantum Computing Since Democritus (Cambridge University Press, 2013)

William J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Princeton University Press, 2012)

Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible (Princeton University Press, 2013)

Dennis Shasha, Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists (first published 1995; Springer, 2008)

 

Credits

Role Contributor
PresenterMelvyn Bragg
Interviewed GuestColva Roney-Dougal
Interviewed GuestTimothy Gowers
Interviewed GuestLeslie Ann Goldberg
ProducerSimon Tillotson

Featured in...

The In Our Time Listeners' Top 10

Hildegard of Bingen

If you’re new to In Our Time, this is a good place to start.

The Matter of the North

BBC_R4_MELVYN_BRAGG_AHW-1920.jpg

Melvyn Bragg explores the pivotal role of England's north in shaping modern Britain.

In Our Time podcasts

In Our Time podcasts

Every episode of In Our Time is available to download.

Arts and Ideas podcast

Arts and Ideas podcast

Download the best of Radio 3's Free Thinking programme.

Related Links