News for hackers. Stuff that matters.
Re:Solving NP-hard puzzles with the oldest trick in the book by lostmsu on Friday October 15, 2021 @03:56PM (#28882382)
lim (k -> 0) (n^k / (k!)) is actually 0. k! grows faster than n^k for any constant n.
Re:Solving NP-hard puzzles with the oldest trick in the book by contravariant on Saturday October 16, 2021 @09:56AM (#28887909)
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!.
Re:Solving NP-hard puzzles with the oldest trick in the book by taintegral on Friday October 15, 2021 @07:17PM (#28884231)
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.
Re:Solving NP-hard puzzles with the oldest trick in the book by lostmsu on Saturday October 16, 2021 @12:25AM (#28885543)
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.