  In this paper we study the complexity of factorization of polynomials in the
free noncommutative ring $\mathbb{F}\langle x_1,x_2,\dots,x_n\rangle$ of
polynomials over the field $\mathbb{F}$ and noncommuting variables
$x_1,x_2,\ldots,x_n$. Our main results are the following.
  Although $\mathbb{F}\langle x_1,x_2,\dots,x_n \rangle$ is not a unique
factorization ring, we note that variable-disjoint factorization in
$\mathbb{F}\langle x_1,x_2,\dots,x_n \rangle$ has the uniqueness property.
Furthermore, we prove that computing the variable-disjoint factorization is
polynomial-time equivalent to Polynomial Identity Testing (both when the input
polynomial is given by an arithmetic circuit or an algebraic branching
program). We also show that variable-disjoint factorization in the black-box
setting can be efficiently computed (where the factors computed will be also
given by black-boxes, analogous to the work [KT91] in the commutative setting).
  As a consequence of the previous result we show that homogeneous
noncommutative polynomials and multilinear noncommutative polynomials have
unique factorizations in the usual sense, which can be efficiently computed.
  Finally, we discuss a polynomial decomposition problem in $\mathbb{F}\langle
x_1,x_2,\dots,x_n\rangle$ which is a natural generalization of homogeneous
polynomial factorization and prove some complexity bounds for it.
