Issue 8 - Christmas 2001
Back in February, The Sum readers took part in a nationwide experiment to see if Murphy's Law of Toast really did ruin breakfasts everywhere, or if it is just a case of bad luck. After nearly 10,000 toast-drops, you proved that it does indeed, but due to height and not butter.
Now, top maths-bod Ian Stewart, writing in the New Scientist, claims that the existence of Murphy's law means that no-one will ever be able to solve the equation P=NP?
This deceptively simple looking puzzle, unanswered since 1979, has a one million dollar prize attached to it. The mind boggling sum is offered by the Clay Mathematics Institute in the US which was set up by business man Landon T. Clay, to further interest in mathematics. The problem translates as:
can P (something easy to solve) equal NP? (something easy to check)
In this case, P is a question that can be solved by an algorithm, or a program on a computer - so therefore it is computable, whereas NP is something which can't - because there are so many possible answers to check through that it would take too long. The model used in computability theory is the Turing Machine, introduced by Alan Turing (an eminent mathematician portrayed in the recently released film Enigma) in 1936.
Confused? Then check out the Institute website at http://claymath.org/prizeproblems and get thinking. The million bucks is yours if you can prove that P=NP is right, wrong or impossible.
However, if Stewart is right about the workings of Murphy's law in our universe then all the brain-strain could be in vain. He points out that even if someone proved the problem to be decidable using a certain system of mathematics, then it is always possible that someone using a different system could prove it as undecidable. Does Murphy win the prize? Is Murphy's Law in itself P=NP? And so the conundrum will continue forever. Remember, if something can go wrong, it will.
Source: The Guardian Newspaper
|page 1 | 2 | 3 | 4 | 5 | credits|