Hacker News Reader

Comment by robrenaud | Hacker News Reader

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.

View on HN

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.

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.

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.

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.

I didn't say otherwise, and did explain why reducing 3-SAT to this proved NP-completeness.

And unless the game levels get arbitrarilly large, this isn't necessarily "hard".

Reply on news.ycombinator.com