Hacker News Reader

Comment by petters | Hacker News Reader

How is this puzzle NP-hard? Genuine question, because of the number of pieces is bounded, it's solvable with a shortest path in a graph with a polynomial number of nodes.

View on HN

Bounding the maximum number of actors is just an optimization for the cases we want to solve. Of course if you wanted to really solve any case you would need infinite space, and that’s not achievable either. If you desired, you can also just omit that particular optimization. :) I think a better way to phrase it is that we are writing a solver for a reasonable subset of inputs to an NP-hard problem.

Wouldn't the size of the graph grow something like $n^k / k!$ ? This is not polynomial in $k$.

lim (k -> 0) (n^k / (k!)) is actually 0. k! grows faster than n^k for any constant n.

I should have been a bit more careful I suppose, but in practice you can't increase k indefinitely without also increasing n anyway. In particular n >= k, so at worst it would be something like k^k / k!.

Really not sure why the state space would only grow as n^k / k!. As well as what n and k are in this case. Adding more tiles or more actors would both dramatically increase the size of the state space for that input.

That question should go to the parent comment. I only corrected the assumption.

On your comment though, I don't think there's much of "drama" in increasing the state space. Really it is just under 2 bits per cell by width by height. I would say it grows exponentially to the size of the board.

Reply on news.ycombinator.com