In Our Time: Science

P v NP

11.05.2015 - By BBC Radio 4Play

Download our free app to listen on your phone

Download on the App StoreGet it on Google Play

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.

More episodes from In Our Time: Science