Polynomial Whitehead-descent time-complexity conjecture

From papers

Let FrF_r be a free group, let NMinFrNMin\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 wNMinw\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.

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

No solutions have been posted yet.