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

The Russo-Japanese War

The Russo-Japanese War

Melvyn Bragg and guests discuss the conflict between Russia and Japan from February 1904 to September 1905, which gripped the world and had a profound impact on both countries. Wary of Russian dominat...

1 Apr 202148min

David Ricardo

David Ricardo

Melvyn Bragg and guests discuss one of the most influential economists from the age of Adam Smith and Thomas Malthus. Ricardo (1772 -1823) reputedly made his fortune at the Battle of Waterloo, and he...

25 Mar 202149min

The Bacchae

The Bacchae

Melvyn Bragg and guests discuss Euripides' great tragedy, which was first performed in Athens in 405 BC when the Athenians were on the point of defeat and humiliation in a long war with Sparta. The ac...

18 Mar 202152min

The Late Devonian Extinction

The Late Devonian Extinction

Melvyn Bragg and guests discuss the devastating mass extinctions of the Late Devonian Period, roughly 370 million years ago, when around 70 percent of species disappeared. Scientists are still trying...

11 Mar 202149min

The Rime of the Ancient Mariner

The Rime of the Ancient Mariner

In this 900th edition of the programme, Melvyn Bragg and guests discuss one of the best known and most influential of the poems of the Romantic movement. Samuel Taylor Coleridge (1772-1834) wrote The...

4 Mar 202153min

Marcus Aurelius

Marcus Aurelius

Melvyn Bragg and guests discuss the man who, according to Machiavelli, was the last of the Five Good Emperors. Marcus Aurelius, 121 to 180 AD, has long been known as a model of the philosopher king, a...

25 Feb 202152min

Medieval Pilgrimage

Medieval Pilgrimage

Melvyn Bragg and guests discuss the idea and experience of Christian pilgrimage in Europe from the 12th to the 15th centuries, which figured so strongly in the imagination of the age. For those able a...

18 Feb 202150min

The Rosetta Stone

The Rosetta Stone

Melvyn Bragg and guests discuss one of the most famous museum objects in the world, shown in the image above in replica, and dating from around 196 BC. It is a damaged, dark granite block on which y...

11 Feb 202147min

Populært innen Historie

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