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)

The Seventh Seal

The Seventh Seal

In the 1000th edition of In Our Time, Melvyn Bragg and guests discuss arguably the most celebrated film of the Swedish director Ingmar Bergman (1918-2007). It begins with an image that, once seen, st...

19 Okt 202348min

Melvyn Bragg talks to Mishal Husain

Melvyn Bragg talks to Mishal Husain

To mark his 1000th episode of In Our Time, Melvyn Bragg talks to Mishal Husain for Radio 4's Today programme.

19 Okt 202311min

Albert Einstein

Albert Einstein

Melvyn Bragg and guests discuss the man who, in 1905, produced several papers that were to change the world of physics and whose name went on to become a byword for genius. This was Albert Einstein, t...

12 Okt 202349min

Jupiter

Jupiter

Jupiter is the largest planet in our solar system, and it’s hard to imagine a world more alien and different from Earth. It’s known as a Gas Giant, and its diameter is eleven times the size of Earth’s...

27 Juli 202353min

Elizabeth Anscombe

Elizabeth Anscombe

In 1956 Oxford University awarded an honorary degree to the former US president Harry S. Truman for his role in ending the Second World War. One philosopher, Elizabeth Anscombe (1919 – 2001), objected...

20 Juli 202354min

Death in Venice

Death in Venice

Death in Venice is Thomas Mann’s most famous – and infamous - novella. Published in 1912, it’s about the fall of the repressed writer Gustav von Aschenbach, when his supposedly objective appreciation ...

13 Juli 202348min

Oedipus Rex

Oedipus Rex

Sophocles’ play Oedipus Rex begins with a warning: the murderer of the old king of Thebes, Laius, has never been identified or caught, and he’s still at large in the city. Oedipus is the current king ...

6 Juli 202354min

Mitochondria

Mitochondria

Melvyn Bragg and guests discuss the power-packs within cells in all complex life on Earth. Inside each cell of every complex organism there are structures known as mitochondria. The 19th century scien...

29 Juni 202352min

Populärt inom Historia

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