RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1989 Volume 176, Pages 3–52 (Mi znsl4532)

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

N. N. Vorobjov (Jr.)


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

UDC: 519.5+512.46


 English version:
Journal of Soviet Mathematics, 1992, 59:3, 789–814

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024