The Functional Decomposition of Polynomials

Let $f(\vec{x}), h_{1}(\vec{x}),...,h_{d}(\vec{x})$ and $g(\vec{x})$ be elements of the polynomial ring $K [\vec{x}]$ (or "polynomials over $K$"). If $f(\vec{x}) = g(h_{1}(\vec({x}),..., h_{d}(\vec{x})),$ then we call $g, h_{1},..., h{d}$ a functional decomposition of $f$. Polynomial decomposition is an important and interesting problem with a number of applications in computer scinece and computational algebra. Problems related to the decomposition of polynomials have received much attention in the past five years [AT85, BZ85, KL86, Dic87, vzGKL87, vzG87, vzG88, Dic88, KL89] as well as in the less recent past [Rit22, Eng41, Lev41, FM69, DW74]. In fact, the decomposition of polynomials is considered important enough that most major computational algebra systems (SCRATCHPAD II, MAPLE, MATHEMATICA) support polynomial decomposition for univariate polynomials. In this thesis, we examine various problems related to the functional decomposition of polynomials. We will give a brief history of polynomial decomposition, and then give a number of new results, including the first polynomial time algorithms for two important decomposition problems and a proof of the NP-completeness of another interesting polynomial decomposition problem. We will also discuss some ot the applications of polynomial decomposition to problems such as polynomial factorization and computing the inverse of an automorphism over a multivariate polynomial ring. For the latter, we will give the first known polyomial time algorithm