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

Pascal

Pascal

Melvyn Bragg and his guests begin a new series of the programme with a discussion of the French polymath Blaise Pascal. Born in 1623, Pascal was a brilliant mathematician and scientist, inventing one ...

19 Sep 201341min

The Invention of Radio

The Invention of Radio

Melvyn Bragg and his guests discuss the invention of radio. In the early 1860s the Scottish physicist James Clerk Maxwell derived four equations which together describe the behaviour of electricity an...

4 Jul 201341min

Romance of the Three Kingdoms

Romance of the Three Kingdoms

Melvyn Bragg and his guests discuss the Romance of the Three Kingdoms, widely regarded as one of the greatest works of Chinese literature. Written 600 years ago, it is an historical novel that tells t...

27 Jun 201342min

The Physiocrats

The Physiocrats

Melvyn Bragg and his guests discuss the Physiocrats, an important group of economic thinkers in eighteenth-century France. The Physiocrats believed that the land was the ultimate source of all wealth,...

20 Jun 201342min

Prophecy

Prophecy

Melvyn Bragg and his guests discuss the meaning and significance of prophecy in the Abrahamic religions. Prophets, those with the ability to convey divinely-inspired revelation, are significant figure...

13 Jun 201342min

Relativity

Relativity

Melvyn Bragg and his guests discuss Einstein's theories of relativity. Between 1905 and 1917 Albert Einstein formulated a theoretical framework which transformed our understanding of the Universe. The...

6 Jun 201342min

Queen Zenobia

Queen Zenobia

Melvyn Bragg and his guests discuss Queen Zenobia, a famous military leader of the ancient world. Born in around 240 AD, Zenobia was Empress of the Palmyrene Empire in the Middle East. A highly educat...

30 Mai 201342min

Lévi-Strauss

Lévi-Strauss

Melvyn Bragg and his guests discuss the work of the anthropologist Claude Lévi-Strauss. One of twentieth-century France's most celebrated intellectuals, Lévi-Strauss attempted to show in his work that...

23 Mai 201342min

Populært innen Historie

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