Abstract:
Let the polynomials
$P_1,\dots,P_k\in\mathbb{Z}[U,X_1,\dots,X_n]$, $h\in\mathbb{Z}[X_1,\dots,X_n]$
have degrees
$\mathrm{deg}_{U,X_1,\dots,X_n}(P_i)$, $\mathrm{deg}_{X_1,\dots,X_n}(h)<d$
and absolute value of any coefficient of $P_i$ or $h$ is less
then or equal to $2^M$ for all $1\leqslant i\leqslant k$. An algorithm is described
which recognises the consistency in $\mathbb{R}^n$ of the system of
inequalities
$f_1\geqslant0,\dots,f_{k_1}\geqslant0,f_{k_1+1}>0,\dots,f_k>0$
where $f_i(X_1,\dots,X_n)=P_i(e^{h(X_1,\dots,X_n)},X_1,\dots,X_n)$
within the time polynomial in $M$, $(nkd)^{n^4}$. This result is a generalization
of the subexponential-time algorithms for deciding consistency
of systems of polynomial inequalities, which were designed in [4], [5], [23] and can be
considered also as a contribution to the solution of Tarski's decidability problem concerning the
first order theory of reals with exponentiation [1].