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
Perpetual Motion [not-audio_url] [/not-audio_url]

Duration: 45:40
Melvyn Bragg and guests discuss the rise of the idea of perpetual motion and its decline, in the 19th Century, with the Laws of Thermodynamics. For hundreds of years, some of the greatest names in science thought there m…
Extremophiles [not-audio_url] [/not-audio_url]

Duration: 46:27
In 1977, scientists in the submersible "Alvin" were exploring the deep ocean bed off the Galapagos Islands. In the dark, they discovered hydrothermal vents, like chimneys, from which superheated water flowed. Around the…
The Science of Glass [not-audio_url] [/not-audio_url]

Duration: 45:57
While glass items have been made for at least 5,000 years, scientists are yet to explain, conclusively, what happens when the substance it's made from moves from a molten state to its hard, transparent phase. It is said…
The Earth's Core [not-audio_url] [/not-audio_url]

Duration: 46:41
Melvyn Bragg and his guests discuss the Earth's Core. The inner core is an extremely dense, solid ball of iron and nickel, the size of the Moon, while the outer core is a flowing liquid, the size of Mars. Thanks to the m…
The Curies [not-audio_url] [/not-audio_url]

Duration: 47:22
Melvyn Bragg and his guests discuss the scientific achievements of the Curie family. In 1903 Marie and Pierre Curie shared a Nobel Prize in Physics with Henri Becquerel for their work on radioactivity, a term which Marie…
Dark Matter [not-audio_url] [/not-audio_url]

Duration: 45:43
Melvyn Bragg and his guests discuss dark matter, the mysterious and invisible substance which is believed to make up most of the Universe. In 1932 the Dutch astronomer Jan Oort noticed that the speed at which galaxies mo…
The Photon [not-audio_url] [/not-audio_url]

Duration: 45:02
Melvyn Bragg and his guests discuss the photon, one of the most enigmatic objects in the Universe. Generations of scientists have struggled to understand the nature of light. In the late nineteenth century it seemed clea…
Behavioural Ecology [not-audio_url] [/not-audio_url]

Duration: 45:35
Melvyn Bragg and guests discuss Behavioural Ecology, the scientific study of animal behaviour.What factors influence where and what an animal chooses to eat? Why do some animals mate for life whilst others are promiscuou…
Brunel [not-audio_url] [/not-audio_url]

Duration: 44:44
Melvyn Bragg and guests discuss Isambard Kingdom Brunel, the Victorian engineer responsible for bridges, tunnels and railways still in use today more than 150 years after they were built. Brunel represented the cutting e…
Nuclear Fusion [not-audio_url] [/not-audio_url]

Duration: 46:55
Melvyn Bragg and his guests discuss nuclear fusion, the process that powers stars. In the 1920s physicists predicted that it might be possible to generate huge amounts of energy by fusing atomic nuclei together, a reacti…