News for hackers. Stuff that matters.
Re:Android Game "Push Down" shown to be NP-Complete by anigbrowl on Monday May 03, 2010 @02:31PM (#1315599)
Neat 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.
Re:Android Game "Push Down" shown to be NP-Complete by SandB0x on Monday May 03, 2010 @02:43PM (#1315644)
Sorry 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?
Re:Android Game "Push Down" shown to be NP-Complete by anigbrowl on Monday May 03, 2010 @02:49PM (#1315658)
I 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.

Re:Android Game "Push Down" shown to be NP-Complete by SandB0x on Monday May 03, 2010 @05:24PM (#1316144)
Aha. 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.
Re:Android Game "Push Down" shown to be NP-Complete by jrockway on Monday May 03, 2010 @03:25PM (#1315801)
Or, people just like their phones to make noise. That's my guess.
Re:Android Game "Push Down" shown to be NP-Complete by fabjan on Monday May 03, 2010 @03:32PM (#1315825)
I'm sorry to say you are wrong and parent is correct :(
Re:Android Game "Push Down" shown to be NP-Complete by jrockway on Monday May 03, 2010 @06:04PM (#1316249)
If it's a privacy thing, then why is it a setting? If I turn the sound off, then I can take all the upskirt pictures I want.
Re:Android Game "Push Down" shown to be NP-Complete by diophant on Tuesday May 04, 2010 @05:22AM (#1317535)
Wow, 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.
Re:Android Game "Push Down" shown to be NP-Complete by jganetsk on Monday May 03, 2010 @03:02PM (#1315719)
Based 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.
Re:Android Game "Push Down" shown to be NP-Complete by iskander on Monday May 03, 2010 @03:19PM (#1315780)
I 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.
Re:Android Game "Push Down" shown to be NP-Complete by BoppreH on Monday May 03, 2010 @03:32PM (#1315827)
That'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.

Re:Android Game "Push Down" shown to be NP-Complete by robrenaud on Monday May 03, 2010 @03:39PM (#1315846)
His 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.

Re:Android Game "Push Down" shown to be NP-Complete by BoppreH on Monday May 03, 2010 @04:32PM (#1315978)
I 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 ) can be mapped in a boolean equation.

Re:Android Game "Push Down" shown to be NP-Complete by robrenaud on Monday May 03, 2010 @05:11PM (#1316106)
Ah, 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.

Re:Android Game "Push Down" shown to be NP-Complete by devinj on Monday May 03, 2010 @05:56PM (#1316227)
No, NP Completeness states that you can go either way.

Specifically: A problem X is NP Complete if:

1: X is in NP.

2: Every problem in P can be reduced to X in polynomial time.

We have established the first condition by intuition-- pathfinding is easy. Immediately, we know, then, that there exists some way to reduce this to 3-SAT, in a way general for any level. Reducing 3-SAT to this, however, proves the second criterion (because 3-SAT is NP-complete, so by doing two reductions you can reduce any NP problem to this, in time at worst the cost of doing sum of the two polynomials describing the complexity of the reductions).

So we can also convert 3-SAT-- or any NP-complete problem, in fact, and even more generally, any NP problem-- to this in poly-time.

Re:Android Game "Push Down" shown to be NP-Complete by Chirono on Monday May 03, 2010 @07:39PM (#1316476)
Indeed. You're correct. But this does show NP-completeness.

A rather incredible theorem is the Cook-Levin theorem which states that any problem that can be verified in polynomial time can reduced to an instance of sat SAT (in polynomial time).

The practical upshot of this is that to show NP-completeness, you only need to provide a polynomial certificate and reduction to SAT, or some other know NP complete problem.

Re:Android Game "Push Down" shown to be NP-Complete by devinj on Monday May 03, 2010 @07:53PM (#1316505)
I didn't say otherwise, and did explain why reducing 3-SAT to this proved NP-completeness.
Re:Android Game "Push Down" shown to be NP-Complete by cookingrobot on Monday May 03, 2010 @03:42PM (#1315858)
And unless the game levels get arbitrarilly large, this isn't necessarily "hard".
Re:Android Game "Push Down" shown to be NP-Complete by hawk on Monday May 03, 2010 @05:39PM (#1316185)
These 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.
Re:Android Game "Push Down" shown to be NP-Complete by leif on Monday May 03, 2010 @04:27PM (#1315965)
File this under "most obvious hardness proofs".
Re:Android Game "Push Down" shown to be NP-Complete by jonursenbach on Monday May 03, 2010 @06:52PM (#1316349)
Any games on the iPhone that are like this?