Let $f(x\_1,\ldots, x\_n)\in\Bbbk [x\_1,\ldots,x\_n]$ be a given polynomial (assume $\Bbbk$ algebraically closed if you want). Suppose that we are given $n$ polynomials $v\_1,\ldots v\_n \in\Bbbk[x\_1,\ldots, x\_n]$. Suppose that we *know* that there exists a polynomial $P(t\_1,\ldots,t\_n)\in\Bbbk[t\_1,\ldots,t\_n]$ such that 


$$f(x\_1,\ldots,x\_n)=P(v\_1(x\_1,\ldots,x\_n),\ldots,v\_n(x\_1,\ldots,x\_n))\in\Bbbk[x\_1,\ldots,x\_n]$$



> 
> How to find $P$ explicitely? Is there a computer program that can easily solve this problem?
> 
> 
> 


I'm also interested in answers under the hypothesis that $v\_1,\ldots, v\_n$ are homogeneus of degrees $d\_1,\ldots, d\_n$ (and possibly some symplifying assumptions on $d\_i$), and/or $f$ is itself homogeneus.


To me this is just a practical question which is natural enough to be asked on MO; I apologize if it is totally trivial for some people more knowledgeable in computational matters.



Simplifying a polynomial
This is the (multivariate) *functional decomposition* problem. It has a long history, going back to 1922 work by Ritt and 1941 work by Engstrom. See the introduction to [Algorithms for the Functional Decomposition of Laurent Polynomials](http://www.csd.uwo.ca/~watt/pub/reprints/2009-calculemus-laurent.pdf) by Stephen Watt for a nice historical overview. You will also be interested in references 1-8 in that paper.


The most recent work (on the multivariate) case that I am aware of is that of [Faugère and Perret](http://dl.acm.org/citation.cfm?id=1576732) (see also the [slides for the talk](http://issac2009.kias.re.kr/ludovic.pdf) and a [journal version](http://www-salsa.lip6.fr/~jcf/Papers/jsc_FP09.pdf)). Their algorithm is non-trivial, and trying to explain it here would amount to reproducing their paper, so I won't do that.


EDIT: Note that most of these algorithms are in two pieces. As was pointed out, just one of these pieces is really needed here. And while GB *can* be used, the good thing about the functional decomposition algorithms is that they are able to use all of the structure present in the problem, which is really too much to ask for from a generic GB.


