Polynomial Whitehead-descent time-complexity conjecture
Polynomial Whitehead-descent time-complexity conjecture
Let be a free group, let be the set of non-minimal elements, and let denote Whitehead complexity. Polynomial Whitehead-descent time-complexity conjecture. The time complexity, or at least the average-case time complexity, of Problem A on inputs is bounded above by
where is a fixed polynomial. This conjecture seeks a polynomial-in-rank complexity bound for solving Problem A on non-minimal inputs, proportional to Whitehead complexity and word length. The source gives no resolution status.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Alexei D. Miasnikov and Alexei G. Myasnikov, “Whitehead method and Genetic Algorithms”, arXiv:math/0304283 (2003).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.