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

Robert Graves

Robert Graves

Melvyn Bragg and guests discuss the author of 'I, Claudius' who was also one of the finest poets of the twentieth century. Robert Graves (1895 -1985) placed his poetry far above his prose. He once de...

7 Nov 202454min

The Haymarket Affair

The Haymarket Affair

Melvyn Bragg and guests discuss the notorious attack of 4th of May 1886 at a workers rally in Chicago when somebody threw a bomb that killed a policeman, Mathias J. Degan. The chaotic shooting that f...

31 Okt 202451min

Wormholes

Wormholes

Melvyn Bragg and guests discuss the tantalising idea that there are shortcuts between distant galaxies, somewhere out there in the universe. The idea emerged in the context of Einstein's theories and ...

24 Okt 20241h

Benjamin Disraeli

Benjamin Disraeli

Melvyn Bragg and guests discuss one of the major figures in Victorian British politics. Disraeli (1804 -1881) served both as Prime Minister twice and, for long periods, as leader of the opposition. Bo...

17 Okt 202451min

Bacteriophages

Bacteriophages

Melvyn Bragg and guests discuss the most abundant lifeform on Earth: the viruses that 'eat' bacteria. Early in the 20th century, scientists noticed that something in their Petri dishes was making ba...

1 Aug 202450min

Monet in England

Monet in England

Melvyn Bragg and guests discuss the work of the great French Impressionist Claude Monet (1840-1926) in London, initially in 1870 and then from 1899. He spent his first visit in poverty, escaping from ...

25 Jul 202450min

Karma

Karma

Melvyn Bragg and guests discuss the doctrine of Karma as developed initially among Hindus, Jains and Buddhists in India from the first millennium BCE. Common to each is an idea, broadly, that you rea...

18 Jul 202450min

Fielding's Tom Jones

Fielding's Tom Jones

Melvyn Bragg and guests discuss "The History of Tom Jones, A Foundling" (1749) by Henry Fielding (1707-1754), one of the most influential of the early English novels and a favourite of Dickens. Coleri...

11 Jul 202454min

Populært innen Historie

rss-dette-ma-aldri-skje-igjen
henrettelsespodden
rss-katastrofe
historier-som-endret-norge
rss-benadet
rss-historiske-romanser-svik-drap-og-kjarlighet
aftenposten-historie
historier-som-endret-verden
med-egne-oyne
rss-nadelose-nordmenn-gestapo
rss-strid-de-norske-borgerkrigene
sektledere
rss-frontkjemperne
rss-bisarr-historie
lille-helvete
taakeprat
rss-gamle-greier
liberal-halvtime
historiepodden
rss-historier-fra-gudbrandsdalen