4 ms·
Wouldn't the size of the graph grow something like $n^k / k!$ ? This is not polynomial in $k$.
by contravariant 5y ago
Wouldn't the size of the graph grow something like $n^k / k!$ ? This is not polynomial in $k$.
- lostmsu 5y agolim (k -> 0) (n^k / (k!)) is actually 0. k! grows faster than n^k for any constant n.
- taintegral 5y agoReally 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.
- lostmsu 5y agoThat 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.
- contravariant 5y agoI 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!.