Average length-reduction complexity conjecture for Whitehead descent
Let be a free group of rank , and let be the set of all non-minimal elements of length . Let denote the length-reducing complexity associated with Whitehead descent. Average length-reduction complexity conjecture. There is a constant such that
This conjecture predicts a rank-dependent limiting upper-average number of length-reducing steps for non-minimal words, and is intended to explain the observed average complexity of the standard Whitehead descent algorithm. The source gives no resolution status.
References
Primary source
Alexei D. Miasnikov and Alexei G. Myasnikov, “Whitehead method and Genetic Algorithms”, arXiv:math/0304283 (2003).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.