Yesterday morning the subject of P vs NP was discussed on BBC Radio 4's In Our Time.
"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. ..."
You might like to listen to the programme. It is entertaining to hear the experts guests, including Tim Gowers of DPMMS, struggle to explain the mathematical concepts of algorithm, P, NP and complexity to layman Melvyn Bragg. Tim suggests one should think of P=practical and NP=not practical. Leslie Ann Goldberg explains the problem of finding a maximal matching, but does not go as far as explaining a polynomial time algorithm. Tim talks of NP-complete problems and calls it "a miracle, not at all obvious", that there is a class of difficult problems that are all equally difficult.
"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. ..."
You might like to listen to the programme. It is entertaining to hear the experts guests, including Tim Gowers of DPMMS, struggle to explain the mathematical concepts of algorithm, P, NP and complexity to layman Melvyn Bragg. Tim suggests one should think of P=practical and NP=not practical. Leslie Ann Goldberg explains the problem of finding a maximal matching, but does not go as far as explaining a polynomial time algorithm. Tim talks of NP-complete problems and calls it "a miracle, not at all obvious", that there is a class of difficult problems that are all equally difficult.
