On Wed, 6 May 2015 23:38:35 -0400, Warren D Smith <warren.wds@gmail.com> wrote:
At what point the diameter will be O(sqrt(N)), O(log(N))? Less than O(log(N))?
--Using my argument last post: None of those things are ever going to happen if your set of primitive moves, is of cardinality <=polynomial(N).
Indeed, it is easy to see that allowing arbitrary 3-permutations as elementary operations will result in node degree of O(N^3), but the diameter will be O(N/2), as in general no more than 2 elements could be put in their desired places at a time. The diameter will be O(N/3) for O(N^4) node degree, etc. However, "swapbits" gives at least O(2^(N/2)) elementary operations, and that's where things should be more interesting. Decomposing an arbitrary permutation to these elementary operations looks nontrivial. Regards, Leo