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.
[ Parent
| on HN ]
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.