P v NP
In Our Time5 Nov 2015

P v NP

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.

Episoder(1086)

The Empire of Mali

The Empire of Mali

Melvyn Bragg and guests discuss the Empire of Mali which flourished from 1200 to 1600 and was famous in the wider world for the wealth of rulers such as Mansa Musa. Mali was the largest empire in west...

29 Okt 201547min

Simone de Beauvoir

Simone de Beauvoir

Melvyn Bragg and guests discuss Simone de Beauvoir. "One is not born, but rather becomes, a woman," she wrote in her best known and most influential work, The Second Sex, her exploration of what it me...

22 Okt 201546min

Holbein at the Tudor Court

Holbein at the Tudor Court

Melvyn Bragg and guests discuss the life and work of Hans Holbein the Younger (1497-1543) during his two extended stays in England, when he worked at the Tudor Court and became the King's painter. Hol...

15 Okt 201546min

Alexander the Great

Alexander the Great

Alexander the Great is one of the most celebrated military commanders in history. Born into the Macedonian royal family in 356 BC, he gained control of Greece and went on to conquer the Persian Empire...

1 Okt 201547min

Perpetual Motion

Perpetual Motion

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 sci...

24 Sep 201545min

Frida Kahlo

Frida Kahlo

Born near Mexico City in 1907, Frida Kahlo is considered one of Mexico's greatest artists. She took up painting after a bus accident left her severely injured, was a Communist, married Diego Rivera, a...

9 Jul 201545min

Frederick the Great

Frederick the Great

Frederick the Great ruled Prussia from 1740 until his death in 1786. Born in 1712, he increased the power of the state, he made Prussia the leading military power in Europe and his bold campaigns had ...

2 Jul 201548min

Extremophiles

Extremophiles

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...

25 Jun 201546min

Populært innen Historie

med-egne-oyne
rss-dette-ma-aldri-skje-igjen
historier-som-endret-norge
henrettelsespodden
rss-benadet
historier-som-endret-verden
rss-katastrofe
rss-nadelose-nordmenn-gestapo
sektledere
aftenposten-historie
rss-strid-de-norske-borgerkrigene
rss-bisarr-historie
rss-frontkjemperne
rss-gamle-greier
rss-politisk-preik
rss-historiske-romanser-svik-drap-og-kjarlighet
historiepodden-ww2
historiepodden
rss-historiepodden-ww2
vare-historier