Polynomial Whitehead-descent time-complexity conjecture

About 23 years old · traced to

Let FrF_r be a free group, let NMin⊂FrNMin\subset F_r be the set of non-minimal elements, and let WC(w)WC(w) 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 w∈NMinw\in NMin is bounded above by

P(r)WC(w)∣w∣,P(r)WC(w)|w|,

where P(r)P(r) 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.

References

Primary source

Alexei D. Miasnikov and Alexei G. Myasnikov, “Whitehead method and Genetic Algorithms”, arXiv:math/0304283 (2003).

Progress summary

Never refreshed

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.