Is it always possible to find polynomials $p(x)$, where the sign of $p(x)$ matches $f(x)$ for every $x$? Given a function $f:\mathbb{R^n}\to \mathbb{R}$ that can be expressed as sum of roots of polynomials, i.e. $f = \sum_{i=0}^k (p_i)^{1/n_i}$ for some polynomials $p_i$ and integers $n_i$. Can one find a polynomial $p:\mathbb{R}^n \to \mathbb{R}$ such that in the domain where both function are defined, we have $p(x_1,\ldots,x_n) \geq 0 \Longleftrightarrow f(x_1,\ldots,x_n)\geq 0$?
For example, $f(x) = \sqrt{x}$, then $p(x) = x$.
$f(x,y) = \sqrt{x^2+y^2}+\sqrt{y}$, then $p(x,y) = x^2+y^2+y$.
However I wasn't able to find one for $f(x,y,z) = \sqrt{x}+\sqrt{y}-z$. It could be I just lack the algebraic skills. 
 A: Your first two examples are always positive, so $p(x)=1$ works as well for the first and $p(x,y)=1$ for the second.  The last has the problem that it goes negative.  Even $\sqrt{x}-z$ fails.  You would like to have $p(x,z)=x-z^2$ which works fine for $z \ge 0$ but not when $z \lt 0$.  $x-z|z|$ does work, but is not a polynomial.
A: You can decompose the region where $f \geq 0$ as a finite union of regions (with disjoint interiors) such that each region is the intersection of a finite number of sets, each set defined by an inequality $p(x_1, \dots, x_n) \geq 0$.  A finite number of polynomials is enough to describe the locus where $f \geq 0$, but more than one polynomial could be necessary.
This is a consequence of Tarski's theorem on quantifier elimination for real-closed fields.
In the comments there was a request to solve the example $f(x,y,z) =  \sqrt{x} + \sqrt{y} - z \geq 0$.
The domain is divided into four regions based on the sign of $x$ and $y$.  In three of the regions $x$ or $y$ is negative and $f$ is undefined.  The region where $f$ exists is the intersection of $x \geq 0$ and $y \geq 0$ and can be divided into two pieces, one with $z \leq 0$ and the second with $z \geq 0$.  In the first piece $f \geq 0$ everywhere.  In the second piece, $f \geq 0$ is equivalent to $z^2 \leq x + y + 2 \sqrt{xy}$ and one can subdivide again according to the sign of $q(x,y,z) = z^2 - x - y$.  Where $q \leq 0$, then $f \geq 0$.  Where $q \geq 0$, the condition is $4xy - q^2 \geq 0$. 
The condition that $f$ is defined and non-negative can always be expressed as a decision tree in which each decision is a test of the sign of a polynomial.
