DiscoverIn Our TimeP vs NP (Summer Repeat)
P vs NP (Summer Repeat)

P vs NP (Summer Repeat)

Update: 2020-07-169
Share

Description

In a programme first broadcast in 2015, 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
Comments 
In Channel
Cave Art

Cave Art

2020-09-2448:34

Pericles

Pericles

2020-09-1749:14

Frankenstein

Frankenstein

2020-03-1955:18

The Covenanters

The Covenanters

2020-03-1254:01

Paul Dirac

Paul Dirac

2020-03-0550:58

The Valladolid Debate

The Valladolid Debate

2020-02-2053:12

George Sand

George Sand

2020-02-0655:05

Alcuin

Alcuin

2020-01-3056:14

Solar Wind

Solar Wind

2020-01-2355:22

Catullus

Catullus

2020-01-0952:43

Tutankhamun

Tutankhamun

2019-12-2653:39

Auden

Auden

2019-12-1953:33

Coffee

Coffee

2019-12-1255:42

Lawrence of Arabia

Lawrence of Arabia

2019-12-0552:15

loading
Download from Google Play
Download from App Store
00:00
00:00
1.0x

0.5x

0.8x

1.0x

1.25x

1.5x

2.0x

3.0x

Sleep Timer

Off

End of Episode

5 Minutes

10 Minutes

15 Minutes

30 Minutes

45 Minutes

60 Minutes

120 Minutes

P vs NP (Summer Repeat)

P vs NP (Summer Repeat)

BBC Radio 4