5 ms·
Android Game "Push Down" shown to be NP-Complete
- anigbrowl 16y agoNeat result, and neat marketing for a neat game - I like this genre. also impressive was the QR code on the homepage - I just installed it by pointing my phone at my monitor. Woah.
- SandB0x 16y agoSorry if this is a bit dense: I've had to download a 3rd party app to read qr codes on my Magic. Is there an built in/default reader that I am unable to find?
- anigbrowl 16y agoI used Google Goggles which is preloaded on my Nexus One. The only thing I dislike about it is the camera shutter noise (unless you silence the phone first). I presume this is to discourage covert intrusions on people's privacy.
- jrockway 16y agoOr, people just like their phones to make noise. That's my guess.
- SandB0x 16y agoAha. Thanks, Goggles does work. The shutter noise might be in part so you and the subject can tell when the picture has been taken. There's been a lot of lag on every phone I've owned and the previews can be jerk, leading to "oops, let's try again" syndrome.
- jganetsk 16y agoBased on the description in this blog post, this proof shows that the game is NP-hard. They have not indicated that they proved that it was NP-complete.
- iskander 16y agoI haven't played this game but it looks like the certificate is just the solved level-- verifying that a cleared path exists can definitely be done in time polynomial with the level size.
- BoppreH 16y agoThat's very interesting, but I didn't understand if all the game is NP-Complete or just that level. The example strikes me as a level specifically designed to look like a boolean equation, while the other levels in the app website are quite different.
- robrenaud 16y agoHis game being NP-complete means that if you write a program that can efficiently solve every instance of puzzle that is provided by his game, you can efficiently solve NP-complete problems. It doesn't make sense to consider any particular level as NP-complete or not, much like it doesn't make sense to consider any particular boolean proposition as NP-complete or not. Even a particularly complicated level or a particularly complicated formula has a trivial program solving it, one that simply prints the solution to that particular puzzle/level without doing any real computation at all.
- cookingrobot 16y agoAnd unless the game levels get arbitrarilly large, this isn't necessarily "hard".
- BoppreH 16y agoI understand what NP-complete means and that for a single problem there will always be a particular solution that just prints the solution. But in the article is said: The proof is surprisingly simple and he did it by showing how the boolean satisfiability problem (SAT) can be mapped onto a level in the game. And only an example level was given, one that looks like it was designed for that purpose. What I can't understand is how a "real" level of the game (like this one: http://bit.ly/bOWbgi http://bit.ly/bOWbgi ) can be mapped in a boolean equation.
- robrenaud 16y agoAh, but you see, there doesn't need to be bijection between his level and SAT problems. There only needs to be a function that when given an arbitrary SAT instance (your "boolean equation") and a blackbox way of solving his puzzle problems can solve that SAT instance. The proof of NP-hardness is basically For every instance of a SAT problem, there exists some puzzle whose solution encodes the SAT solution. You are asking about For every instance of his puzzle, does there exist a SAT formula solved by this puzzle Which is a different question.
- leif 16y agoFile this under "most obvious hardness proofs".
- hawk 16y agoThese proofs aren't really that interesting, it's more of an exercise really... most solitaire games with certain properties are NP-complete and most 2-player games are PSPACE-complete.
- jonursenbach 16y agoAny games on the iPhone that are like this?
- diophant 16y agoWow, I never guessed that my simple proof achieved so much resonance! You're right in the comments that the proof just shows the NP-hardness. I ommitted the other part of the proof, because it seemed obvious to me - as others already said, you just have to find a solution of the level by nondeterministically "guessing" and verifying it. Of course, the game levels can get arbitrarily large. You have to assume this for any problem, otherwise there is only a finite (and therefore constant) number of configurations of the problem, and checking them can be done in constant time. Btw., I also found a direct reduction from directed Hamiltonian cycle. The proof is a little bit more complicated, the idea is that you have to collect a key in each node, and that you can leave each node only once, i.e., leaving a node on one edge will block all other outgoing edges of the node. Another technical difficulty was to create crossing edges. If you are interested in the proof, I'll ask Holger to put the example level in his blog.