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.

Avsnitt(1080)

A Room of One's Own

A Room of One's Own

Melvyn Bragg and guests discuss Virginia Woolf's highly influential essay on women and literature, which considers both literary history and future opportunity. In 1928 Woolf gave two lectures at Cam...

27 Apr 202354min

Solon the Lawgiver

Solon the Lawgiver

Melvyn Bragg and guests discuss Solon, who was elected archon or chief magistrate of Athens in 594 BC: some see him as the father of Athenian democracy. In the first years of the 6th century BC, the ...

20 Apr 202351min

Mercantilism

Mercantilism

Melvyn Bragg and guests discuss how, between the 16th and 18th centuries, Europe was dominated by an economic way of thinking called mercantilism. The key idea was that exports should be as high as ...

13 Apr 202357min

The Ramayana

The Ramayana

Melvyn Bragg and guests discuss the Ramayana, the ancient Hindu epic which is regarded as one of the greatest works of world literature. Its importance in Indian culture has been compared to that of t...

6 Apr 202349min

Megaliths

Megaliths

Melvyn Bragg and guests discuss megaliths - huge stones placed in the landscape, often visually striking and highly prominent. Such stone monuments in Britain and Ireland mostly date from the Neolithi...

30 Mars 202350min

Paul Erdős

Paul Erdős

Paul Erdős (1913 – 1996) is one of the most celebrated mathematicians of the 20th century. During his long career, he made a number of impressive advances in our understanding of maths and developed w...

23 Mars 202351min

Stevie Smith

Stevie Smith

In 1957 Stevie Smith published a poetry collection called Not Waving But Drowning – and its title poem gave us a phrase which has entered the language. Its success has overshadowed her wider work as t...

16 Mars 202353min

Chartism

Chartism

On 21 May 1838 an estimated 150,000 people assembled on Glasgow Green for a mass demonstration. There they witnessed the launch of the People’s Charter, a list of demands for political reform. The cha...

9 Mars 202351min

Populärt inom Historia

massmordarpodden
kod-katastrof
motiv
historiska-brott
olosta-mord
p3-historia
historiepodden-se
rss-historien-om
rss-seriemordarpodden
rss-massmordarpodden
rss-historiska-brottslingar
historianu-med-urban-lindstedt
rss-brottsligt
krigshistoriepodden
rss-arkiv-stieg
palmemordet
harrisons-dramatiska-historia
oppet-fall
nu-blir-det-historia
militarhistoriepodden