Eternity II November 28, 2007Posted by Andre Vellino in Logic.
If you think that P=NP is a purely theoretical question, think again. It’s been more than 30 years now since Cook and Reckow’s seminal paper “On the lengths of proofs in the propositional calculus” and the Millenium Prize (from the Clay Mathematics Institute) for solving P=NP is currently $1M.
It seems bizarre that the stakes are even higher ($2M) for solving a particular instance of an NP-complete problem – the Eternity II puzzle. The prize is a clever marketing ploy to induce the foolhardy to buy it.
Eternity II is a variant on Tetravex and prospective buyers are well advised to read the proof by Takenga and Walsh that Tetravex is NP-complete or the paper “Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity“. The reader of either paper will quickly conclude that there are easier ways to make $2M – you could take another NP-Complete problem, make a game out of it and sell the game🙂 – or you could crack the public key encryption in SSL and become an internet pirate.
Better still, you could just buy a lottery ticket. The probability of your winning a lottery jackpot are quite a bit higher than solving Eternity II. From his explanation of the design of Eternity II, Brendan Owen estimates that the best possible algorithms for this puzzle will require the exploration of 2×10^47 possibilities.
So if you don’t mind making Eternity II’s inventor – a British Viscount who denies the anthropogenic nature of Global Warming and admires Margaret Thatcher – more rich than he already is, then this game’s for you!