202 // Don't Get the Goat

different from NP, or indeed for proving that, on the contrary, the two are equal.

As a final twist, it turns out that all likely candidates to show that P 6¼ NP are in some sense equivalent. A problem is called NP- complete if a polynomial-time algorithm to solve that particular problem automatically leads to a polynomial-time algorithm to solve any NP problem. Almost any reasonable candidate for proving that P 6¼ NP is known to be NP-complete. The nasty consequence of this fact is that no particular candidate is likely to be more approachable than any of the others ­ they all live or die together. In short: we know why P¼NP? must be a very hard problem, but that doesn't help us to solve it.

...........................................

I suspect that there are far easier ways to make a million.

Don't Get the Goat There used to be an American game show, hosted by Monty Hall, in which the guest had to choose one of three doors. Behind one was an expensive prize ­ a sports car, say. Behind the other two were booby prizes ­ goats.

After the contestant had chosen, Hall would open one of the other doors to reveal a goat. (With two doors to choose from, he could always do this ­ he knew where the car was.) He would then offer the contestant the chance to change their mind and choose the other unopened door.

Hardly anyone took this opportunity ­ perhaps with good reason, as I'll eventually explain. But for the moment let's take the problem at face value, and assume that the car has equal probability (one in three) of being behind any given door. We'll assume also that everyone knows ahead of time that Hall always offers the contestant a chance to change their mind, after revealing a goat. Should they change?

The argument against goes like this: the two remaining doors are equally likely to conceal a car or a goat. Since the odds are fifty­fifty, there's no reason to change.

two page view?

all devices