Eternity II November 28, 2007
Posted by Andre Vellino in Logic.trackback
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!
Synthèse 
I admit that I am too lazy to read the paper, but are you certain he formally proves that you need to explore 10^47 possibilities?
One thing that complexity theorists seem to have a hard time doing is coming up with sensible lower bounds. Most times, people can prove that the problem requires x*n operations for some x, using information theoretical arguments… but that’s often pretty much it.
In fact, the lack of progress on the road to P=NP is related to this difficulty, isn’t it?
As an example, in the game of checkers to fully enumerate all possibilities requires a nasty amount of time. However, Jonathan was able to do without this impossibly hard enumeration and still beat the game:
http://www.daniel-lemire.com/blog/archives/2007/10/24/play-the-strongest-checkers-program-in-the-world/
In any case, I am less interested in P=NP, than I am interested in a having good strategies to come up with computational lower bounds. Very often, I use algorithms with only a vague idea that it is the best I can do. Most often, I only know it is “optimal” because nobody was able to find anything better. Hardly satisfying! This annoys the heck out of me.
You’re quite right, Daniel, that coming up with good lower bounds is tricky. Brendan Owen’s estimates for Eternity II are, I think, empirical, and based on a given computational strategy (naive backtracking). At least, that’s what I could gather from his postings on:
http://games.groups.yahoo.com/group/eternity_two/
I don’t know whether Brendan is a mathematician or a theoretician – he doesn’t have anything to do with the papers to which I refer that give proofs of NP-Completeness.
It will be interesting to see if anyone comes up with a strategy (even a clever enumeration strategy) to beat Tetravex-type puzzles. However, the fact that a couple of Random Graph theorists Alex Selby (http://www.archduke.org/) and Oliver Riordan (http://www2.maths.ox.ac.uk/~riordan/) had a hand in Eternity II leads me to suspect that the solution won’t be found so easily.
Hello, I have a question if anybody foundts that np=p, solving any other np complete problem, like 3sat, or subset sum, then what, is the reduction, that could be aplied for solving ethernity 2 game, is there another paper that show that solution?
More news and combinations computations here :
http://eternity2blogger.over-blog.com/
Regards,
Eternity II Blogger.
lemire: The field of Computational Complexity Theory has primarily branched into two areas over the last one or two decades. One of them is called Circuit Complexity and does provide lower bounds on the number of operations necessary to compute various classes of functions. It is quite a respected area that has come a long way (but is currently not experiencing as much progress as in the past?). I think that branch has a high chance of one day resolving the P vs. NP problem.
In the other branch, often called higher complexity theory, we do pretty much same thing except we look at higher complexity classes, find relations between them, and find ways to deal with the hardness of the problems, e.g., with approximation. One topic in this field is that of exact algorithms, which derives upper and lower bounds on the computational resources of NP-hard problems resting on the assumption that there is no subexponential-time algorithm for 3SAT (called the exponential-time hypothesis). For Eternity II-type puzzles, it should be quite doable to derive such lower bounds from that hypothesis.
Although, sorry, the latter branch only cares about solving the problem in general (not specific instances, like ordinary checkers) and the asymptotic behavior of the resources needed, which you lamented.
Jaime Bonilla: The definition of an NP-easy problem is simply that a solution can be verified in polynomial time. This is typically a property that one can verify with a glance at the problem. Given a solution to the Eternity II puzzle, I can just check that all of the edges match. The definition of an NP-hard problem is that every NP-easy problem should be reformulated as an instance to the problem. In other words, if we could solve that problem, we could solve all NP-easy problems. This is the highlight of the original paper by Cook and Reckow: they showed that 3SAT is NP-hard. That’s the only paper you need to read (or rather, a textbook) for how to solve the other NP-easy problems given that there is some NP-hard problem in P (which is equivalent to P=NP). To give you a quick idea of the answer: if someone showed problem X to be NP-hard, they must have showed to reformulate some problem A to X, and we knew B could be formulated as A, and C as B, etc., and eventually that 3SAT can be formulated as C, and we know 3SAT can simulate a non-deterministic polynomial-time Turing machine (NTIME(poly)), i.e. one that guesses the answer and then checks it in polynomial time. So given that you just follow all of these reductions, you get a polynomial-time simulation program for NTIME(poly) from the polynomial-time program for A.
The hard work for showing that a problem is NP-complete (=NP-easy and NP-hard) is pretty much always to show that the problem is NP-hard. That is what the paper by Demaine and Demaine show. Namely, that Eternity II is also NP-hard and so a polynomial-time solution to it (in the general case) gives a polynomial-time algorithm for every NP-easy problem.
Hi.. sorry to reply to a 7 year old post.
Do you know how to convert eternity II to a SAT problem?
How do you mean? Any old reduction to SAT or one that is particularly suited for SAT solvers or something?
Yes, 3SAT… suited for a SAT solver (but whether any existing SAT solver can solve it is irrelevant)
Perhaps I am mistaken but why does not the “obvious thing” work? E.g. how would you do the reduction for the 2×2 case and no rotations?
Sorry. I am not a mathematician. I don’t get what you mean at all.
I mean, it seems like a simple exercise to make the reduction. Are you a coder? E.g. if you imagine that you had arbitrary variables, how would you do the reduction if the puzzle only consisted of two by two pieces?
I am just a beginner. It’s okay then. I am just asking out of curiosity rather than needing a solution.
I expect Isacc means – a “natural” mapping from Eternity to SAT. For example, the “pigeon-hole problem” (can you fit N pigeons into N-1 holes?) has a “natural” mapping into boolean propositional formula e.g. (for 3 pigeons in 2 holes) …. (p11 v p12 ) & (p21 v p22 ) & (p31 v p32) & ~(p11&p21) & ~(p12 & p22) etc.
And the answer is – I don’t know but I expect so.
Yup. That’s what I meant.
fun88
Eternity II | Synthèse