P v NP

In Our Time

BBC

History

4.6 • 9.2K Ratings

🗓️ 5 November 2015

⏱️ 46 minutes

🔗️ Recording | iTunes | RSS

🧾️ Download transcript

Summary

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.

Transcript

Click on a timestamp to play from that location

0:00.0	Thank you for downloading this episode of In Our Time for more details about In Our Time
0:04.0	and for our terms of use, please go to bbc.co.uk slash radio for.
0:09.0	I hope you enjoy the program.
0:11.0	Hello, the problem of P versus NP is so difficult to solve.
0:15.0	There's a $1 million prize on offer from the Clay Mathematical Institute for the first
0:20.0	person to come up with a solution.
0:21.8	At its heart is the question, are there problems for which the answers can be checked
0:25.6	by computers but not found in a reasonable time, or can all answers be found easily as
0:30.9	well as checked if only we knew how.
0:33.6	It's intrigued mathematicians and computer scientists since Alan Turing in the 1930s found
0:38.5	that some programs, given a problem, could run indefinitely without finding the answer.
0:43.5	That's a story of today's supercomputers as it was in his day.
0:47.1	Resting on P versus NP is the safety of online banking and all online transactions which
0:52.0	are currently secure.
0:53.6	If answers can be found as easily as checked, computers could crack passwords in moments.
0:58.5	To solve thousands of practical problems is also in sight.
1:02.2	We'd need to discuss, but not perhaps solve the problem of P versus NP.
1:06.5	I call Veroni Dugel, reader in pure mathematics at the University of St Andrews, Timothy Gowers,
1:12.4	Royal Society Research Professor in Mathematics at the University of Cambridge, and Leslie
1:16.5	Ann Goldberg, Professor of Computer Science and Fellow of St Edmund Hall University of Oxford.
1:22.5	Colver, Rony, Dover, what was Alan Turing doing in 1936 and led him to this?
1:29.2	Alan Turing was interested in trying to solve some problems in the foundations of mathematics,
	...

Please login to see the full transcript.

Previous episode | Next episode

Disclaimer: The podcast and artwork embedded on this page are from BBC, and are the property of its owner and not affiliated with or endorsed by Tapesearch.

Generated transcripts are the property of BBC and are distributed freely under the Fair Use doctrine. Transcripts generated by Tapesearch are not guaranteed to be accurate.