Average length-reduction complexity conjecture for Whitehead descent
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.