On the complexity of noncommutative polynomial factorization

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring F〈x1,x2,…,xn〉 of polynomials over the field F and noncommuting variables x1,x2,…,xn. Our main results are the following: