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(1077)

Catherine of Aragon

Catherine of Aragon

Melvyn Bragg and guests discuss Catherine of Aragon (1485-1536), the youngest child of the newly dominant Spanish rulers Ferdinand and Isabella. When she was 3, her parents contracted her to marry Ar...

13 Mar 202552min

Sir John Soane

Sir John Soane

Melvyn Bragg and guests discuss the architect Sir John Soane (1753 -1837), the son of a bricklayer. He rose up the ranks of his profession as an architect to see many of his designs realised to great ...

6 Mar 202553min

Pope Joan

Pope Joan

Melvyn Bragg and guests discuss a story that circulated widely in the middle ages about a highly learned woman who lived in the ninth century, dressed as a man, travelled to Rome, and was elected Pope...

27 Feb 202546min

Socrates in Prison

Socrates in Prison

Melvyn Bragg and guests discuss Plato's Crito and Phaedo, his accounts of the last days of Socrates in prison in 399 BC as he waited to be executed by drinking hemlock. Both works show Socrates prepar...

20 Feb 202550min

The Battle of Valmy

The Battle of Valmy

Melvyn Bragg and guests discuss one of the most consequential battles of recent centuries. On 20th September 1792 at Valmy, 120 miles to the east of Paris, the army of the French Revolution faced Prus...

13 Feb 202547min

Slime Moulds

Slime Moulds

Melvyn Bragg and guests discuss slime mould, a basic organism that grows on logs, cowpats and compost heaps. Scientists have found difficult to categorise slime mould: in 1868, the biologist Thomas Hu...

30 Jan 202551min

Vase-mania

Vase-mania

Melvyn Bragg and guests discuss eighteenth century 'vase-mania'. In the second half of the century, inspired by archaeological discoveries, the Grand Tour and the founding of the British Museum, parts...

23 Jan 202556min

Plutarch's Parallel Lives

Plutarch's Parallel Lives

Melvyn Bragg and guests discuss the Greek biographer Plutarch (c46 AD-c120 AD) and especially his work 'Parallel Lives' which has shaped the way successive generations see the Classical world. Plutarc...

16 Jan 202556min

Populært innen Historie

henrettelsespodden
rss-dette-ma-aldri-skje-igjen
rss-katastrofe
rss-historiske-romanser
historier-som-endret-norge
rss-benadet
historier-som-endret-verden
aftenposten-historie
rss-frontkjemperne
sektledere
rss-gamle-greier
rss-nadelose-nordmenn-gestapo
med-egne-oyne
rss-strid-de-norske-borgerkrigene
taakeprat
historiepodden-ww2
undersattene
sannhet-eller-konspirasjon
vare-historier
historiepodden