Thank you for downloading this episode of In Our Time, for more details about in our time, and for our terms of use please go to BBC.co.uk.

UK slash Radio 4. I hope you enjoy the program.

Hello, the problem of P versus NP is so difficult to solve there's a $1 million prize on offer

from the Clay Mathematical Institute for the first person to come up with a 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,

or can all answers be found easily as well as checked if only knew how.

Its intrigued mathematicians and computer scientists since Alan Turing in the 1930s

found that some programs given a problem could run indefinitely without finding the answer. That's as true of today's

supercomputers as it was in his day. Resting on P versus NP is the safety of online banking

and all online transactions which are currently secure.

If answers can be found as easily as checked, computers could crack passwords in moments

to solve thousands of practical problems is also in sight.

With me to discuss, but not perhaps solve the problem of

P versus N. P. A Colver Roney Doagle, 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.

Colver Rone Duva, what was Alan Turing doing in 1936 and led him to this?

Alan Turing was interested in trying to solve some problems in the foundations of mathematics and how that links in with this is he started thinking about how you could define whether or not it was possible to solve a problem and this led him at the bright young age of 22 to essentially

invent our modern notion of a computer. It was a little while before computers

were actually built but he defined an abstract machine that we now call a Turing machine and said that the properties it needed to have is that it should be able to read input, it should be able to write output, and it should be able to decide what to do based only on what state it was in then

...