Deciding consistency of systems of polynomial in exponent inequalities in subexponential time

N. N. Vorobjov (Jr.)

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 4, Tome 176 (1989), pp. 3-52

Résumé

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].