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

The Age of Doubt

The Age of Doubt

Melvyn Bragg examines the spread of religious doubt over the last three centuries. Nietzsche proclaimed that God was Dead in 1882, Hegel in fact beat him to it apprising his Berlin students of God’s d...

9 Mar 200028min

Metamorphosis

Metamorphosis

Melvyn Bragg and guests discuss the Roman poet Ovid and explore the theme of metamorphosis from the transformation of Narcissus to the bug of Kafka’s story, and beyond. Ovid wrote at the beginning of ...

2 Mar 200028min

Grand Unified Theory

Grand Unified Theory

Melvyn Bragg examines 20th century physics’ quest for the ultimate theory of everything. Einstein left us with his theory of General Relativity, which explained how gravity works on the scale of stars...

24 Feb 200028min

Reading

Reading

Melvyn Bragg and guests discuss the history of the politics and practice of reading. Gustave Flaubert’s sage advice to us was: “Do not read, as children do, to amuse yourself, or like the ambitious, f...

17 Feb 200028min

Goethe and the Science of the Enlightenment

Goethe and the Science of the Enlightenment

Melvyn Bragg and guests discuss Johann Wolfgang von Goethe, the great poet and dramatist, famous for Faust, for The Sorrows of Young Werther, for Storm und Drang and for being a colossus in German lit...

10 Feb 200028min

Republicanism

Republicanism

Melvyn Bragg examines how English republicanism has developed from Cromwell to the present day. Before the French Revolution, before the American Declaration of Independence, before Rousseau, Thomas P...

3 Feb 200028min

Economic Rights

Economic Rights

Melvyn Bragg and guests discuss economic rights. Is democracy the truest conduit of capitalism, or do the forces that make us rich run counter to the democratic institutions that safeguard our rights?...

27 Jan 200027min

Masculinity in Literature

Masculinity in Literature

Melvyn Bragg investigates masculinity in literature. Ernest Hemingway wrote in The Old Man and the Sea, “A man can be destroyed but not defeated”. In a time when traditional male roles have been syste...

20 Jan 200028min

Populært innen Historie

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