Sometimes, when an algorithmic decision problem is known to be solvable, the focus shifts to finding an efficient (e.g. polynomial time) algorithm. In this section, we have collected some especially interesting (in our opinion) problems of this kind. Most of them are motivated by (more or less) practical applications. See also problems (F25), (OR3), (H4).

*(C1) Is there a polynomial time algorithm for solving the word problem in the group Aut(F_n) (with respect to some particular finite presentation), where F_n is the free group of rank n ?   Background

(C2) (S. Ivanov) Let   u, v  be two elements of the free group F_n. According to Whitehead, the problem of detecting whether or not   u  is an automorphic image of   v   is decidable. Is this problem in the class NP (that is, decidable in nondeterministic polynomial time with respect to the maximum of |u|, |v|)?   Background

*(C3) (V.Shpilrain) Is the conjugacy problem in the braid group B_n in the class NP (that is, decidable in nondeterministic polynomial time with respect to the maximum of the lengths |u|, |v|, where u, v are the input words)?   Background

(C4) Is there a subexponential upper bound for the time complexity of Dehornoy's algorithm for solving the word problem in braid groups? (cf. Problem (B8))   Background