P v NP

P v NP

Author: BBC Radio 4 November 5, 2015 Duration: 45:45

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.


Melvyn Bragg and a panel of academic experts gather each week to explore the vast history of scientific thought on In Our Time: Science. This BBC Radio 4 podcast delves far beyond simple explanations, instead tracing the long and often winding paths of discovery that shaped our understanding of the world. Each episode focuses on a single idea, from the concept of zero to the theory of plate tectonics, unpacking its origins, the controversies it sparked, and the key figures who championed or challenged it. You’ll hear lively, in-depth conversations that place science firmly within its human and historical context, revealing how principles we take for granted today were hard-won through centuries of debate, accident, and insight. The discussions are rigorous and accessible, designed for the curious mind eager to appreciate not just what we know, but how we came to know it. By treating science as a deeply historical endeavour, this series offers a richer appreciation of the discipline itself. Tune in for a thoughtful and engaging journey through the experiments, the arguments, and the brilliant flashes of imagination that have defined our quest for knowledge.
Author: Language: English Episodes: 100

In Our Time: Science
Podcast Episodes
Louis Pasteur [not-audio_url] [/not-audio_url]

Duration: 51:08
Melvyn Bragg and guests discuss the life and work of Louis Pasteur (1822-1895) and his extraordinary contribution to medicine and science. It is said few people have saved more lives than Pasteur. A chemist, he showed th…
Pauli's Exclusion Principle [not-audio_url] [/not-audio_url]

Duration: 48:13
After 27 years, Melvyn Bragg has decided to step down from the In Our Time presenter’s chair. With over a thousand episodes to choose from, he has selected just six that capture the huge range and depth of the subjects h…
The Paleocene-Eocene Thermal Maximum [not-audio_url] [/not-audio_url]

Duration: 49:47
Melvyn Bragg and guests discuss the high temperatures that marked the end of the Paleocene and start of the Eocene periods, about 50m years ago. Over c1000 years, global temperatures rose more than 5 C on average and sta…
The Kuiper Belt [not-audio_url] [/not-audio_url]

Duration: 48:11
Melvyn Bragg and guests discuss the Kuiper Belt, a vast region of icy objects at the fringes of our Solar System, beyond Neptune, in which we find the dwarf planet Pluto and countless objects left over from the origins o…
Maths in the Early Islamic World [not-audio_url] [/not-audio_url]

Duration: 49:07
Melvyn Bragg and guests discuss the flourishing of maths in the early Islamic world, as thinkers from across the region developed ideas in places such as Baghdad's House of Wisdom. Among them were the Persians Omar Khayy…
Parasitism [not-audio_url] [/not-audio_url]

Duration: 45:45
Melvyn Bragg and guests discuss the relationship between parasites and hosts, where one species lives on or in another to the benefit of the parasite but at a cost to the host, potentially leading to disease or death of…
Johannes Kepler [not-audio_url] [/not-audio_url]

Duration: 48:42
Melvyn Bragg and guests discuss the German astronomer Johannes Kepler (1571 - 1630). Although he is overshadowed today by Isaac Newton and Galileo, he is considered by many to be one of the greatest scientists in history…
John Dalton [not-audio_url] [/not-audio_url]

Duration: 45:40
The scientist John Dalton was born in North England in 1766. Although he came from a relatively poor Quaker family, he managed to become one of the most celebrated scientists of his age. Through his work, he helped to es…
Plasma [not-audio_url] [/not-audio_url]

Duration: 45:53
Melvyn Bragg and guests discuss plasma, the fourth state of matter after solid, liquid and gas. As over ninety-nine percent of all observable matter in the Universe is plasma, planets like ours, with so little plasma and…
Zeno's Paradoxes [not-audio_url] [/not-audio_url]

Duration: 46:30
After 27 years, Melvyn Bragg has decided to step down from the In Our Time presenter’s chair. With over a thousand episodes to choose from, he has selected just six that capture the huge range and depth of the subjects h…