Shortened

BBC Radio 4 FM

BBC Radio 4 is a radio channel that started transmitting on the 30th September 1967. It replaced BBC Home Service.

BBC Radio 4

Radio 4

Radio 4 (FM)

In Our Time

Discussion & Talk

Podcasts

Factual: History

Melvyn Bragg and guests discuss the ideas, people and events that have shaped our world.

BBC Radio 4 LW

Melvyn Bragg

Colva Roney-Dougal

Timothy Gowers

Leslie Ann Goldberg

Simon Tillotson

In Our Time: P v NP

P v NP

05/11/2015

BBC Radio 4 - In Our Time, P v NP

Melvyn Bragg and guests discuss the mathematical problem of P versus NP.

Melvyn Bragg and guests discuss P versus NP, an unsolved problem in maths that asks if the answers to all problems can be found as easily as they can be checked.

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.

Intelligent speech, the most insightful journalism, the wittiest comedy, the most fascinating features and the most compelling drama and readings anywhere in UK radio.

Accessibility links

Programme Index

In Our Time

P v NP

Contributors

Genres

Formats

Brand

BBC Radio 4 FM

About BBC Radio 4