|
Zapiski Nauchnykh Seminarov 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].
Citation:
N. N. Vorobjov (Jr.), “Deciding consistency of systems of polynomial in exponent inequalities in subexponential time”, Computational complexity theory. Part 4, Zap. Nauchn. Sem. LOMI, 176, "Nauka", Leningrad. Otdel., Leningrad, 1989, 3–52; J. Soviet Math., 59:3 (1992), 789–814
Linking options:
https://www.mathnet.ru/eng/znsl4532 https://www.mathnet.ru/eng/znsl/v176/p3
|
|