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.

Denne episoden er hentet fra en åpen RSS-feed og er ikke publisert av Podme. Den kan derfor inneholde annonser.

Episoder(1096)

The Evolution of Trees

Misha Glenny and guests discuss the earliest evidence we have of the existence of trees and how even plants we might have on windowsills or as vegetables in gardens can and do, in the right conditions...

2 Jul 54min

The Welsh Marches

At the Hay Festival, Misha Glenny and guests discuss the impact of the Norman invasion on the people and land of Wales and across the modern border with England in what became known as The Welsh March...

25 Jun 52min

The Levellers

Misha Glenny and guests discuss the group which came to be known as the Levellers and emerged during what would become arguably one of the bloodiest and most turbulent periods of English history. Afte...

18 Jun 55min

The Garamantes

Misha Glenny and guests discuss an ancient civilisation who lived over 2000 years ago in the southwest of modern-day Libya. During prehistoric times, the Sahara Desert was greener and even had large l...

11 Jun 57min

Joseph Roth

Misha Glenny and guests discuss one of the great writers on Central Europe after the first world war and on the dying of the old orders with the collapse of the Austro-Hungarian empire. As a German s...

4 Jun 55min

Cybernetics

Misha Glenny and guests discuss cybernetics – the field of study which gave us the prefix ‘cyber’ and helped lay the foundations for the information age. After the Second World War, cybernetics emerge...

28 Mai 52min

Indian Indentured Labour

Misha Glenny and guests discuss how, after the abolition of slavery in the British Empire in 1833, sugar planters recruited workers from India to replace or compete with their formerly enslaved labour...

21 Mai 51min

M.C. Escher

Misha Glenny and guests discuss the work of Maurits Cornelis Escher (1898-1972), the graphic artist and printmaker best known for his impossible buildings, paradoxical perspectives, and repeating geom...

14 Mai 55min