RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zap. Nauchn. Sem. POMI: Year: Volume: Issue: Page: Find

 Zap. Nauchn. Sem. LOMI, 1988, Volume 174, Pages 3–36 (Mi znsl4510)

Solving systems of polynomial inequalities over real closed fields in subexponential time

N. N. Vorobjov (Jr.), D. Yu. Grigor'ev

Abstract: Let $\mathbb{Q}_m$ denote the field $\mathbb{Q}(\delta_1,…,\delta_m)$, where $m\geqslant1$, $\mathbb{Q}_0=\mathbb{Q}$ and an element $\delta_m$ is infinitesimal relatively to the elements of the field $\mathbb{Q}_{m-1}$, i.e. $0<\delta_m<a$ for any $0<a\in\mathbb{Q}_{m-1}$. Denote by $\widetilde{\mathbb{Q}}_m$ the real closure of $\mathbb{Q}_m$. A subexponential-time algorithm is described for finding solutions in $\widetilde{\mathbb{Q}}_m$ of a system of polynomial inequalities. In the case $m=0$ (i.e. $\mathbb{Q}_m=\mathbb{Q}$), exponential-time procedures were designed for this problem ([4], [16], [20]). Finally, in [3], [21] the authors proposed subexponential-time algorithm for $m=0$.
Let
$$f_1>0,…,f_{k_1}>0, f_{k_1+1}\geqslant0,…,f_k\geqslant0 \qquad{(1)}$$
be the input system where polynomials $f_1,…,f_k\in\mathbb{Q}_m[X_1,…,X_n]$.
Denote by $V\subset(\widetilde{\mathbb{Q}}_m)^n$ the set of all solutions of (1). For a rational function $\alpha=\alpha_1/\alpha_2\in\mathbb{Q}_m(X_1,…X_n)$ where polynomials $\alpha_1,\alpha_2\in\mathbb{Z}[\delta_1,…,\delta_m][X_1,…,X_n]$ denote by $l(\alpha)$ the maximum bit lengths of the integer coefficients of $\alpha_1$$\alpha_2. Suppose, that the following inequalities are valid:$$ \mathrm{deg}_{\delta_1,…,\delta_m}(f_i)<d_0,\quad \mathrm{deg}_{X_1,…,X_n}(f_i)<d,\quad l(f_i)\leqslant M,\quad1\leqslant i\leqslant k. \qquad{(2)}$$The notation$h_1\leqslant\mathcal{P}(h_2,…,h_t)$for functions$h_1>0,…,h_t>0$means that for suitable natural numbers$p$,$q$an inequality$h_1\leqslant p(h_2\cdots h_t)^q$is true. THEOREM. There is an algorithm which for system (1), satisfying (2), produces$a$finite set$\mathcal{J}\subset V$having nonempty intersection with each component of connectivity of$V$, with the number of points in$\mathcal{J}$not exceeding$\mathcal{P}((kd)^{n^2})$. The running time of the algorithm is less than$\mathcal{P}(M,((kd)^n d_0)^{m+n})$. For every point$(\xi_1,…,\xi_n)\in\mathcal{J}$the algorithm constructs an irreducible over$\mathbb{Q}_m$polynomial$\Phi\in\mathbb{Q}_m[Z]$, and the expressions$\xi_i=\xi_i(\omega)=\sum\limits_{0\leqslant j<\mathrm{deg}(\Phi)}\alpha_j^{(i)}\omega^j\in\mathbb{Q}_m[\omega]$, where$\alpha_j^{(i)}\in\mathbb{Q}_m$($1\leqslant i\leqslant n$) and$\omega\in\widetilde{\mathbb{Q}}_m$,$\Phi(\omega)=0$. The constructed polynomials and expressions satisfy the following bounds:$\mathrm{deg}_{\delta_1,…,\delta_m,X_1,…,X_n}(\Phi)\leqslant d_0\mathcal{P}((kd)^n)$;$l(\Phi)$,$l(\xi_j(\omega))\leqslant(M+md_0)\mathcal{P}((kd)^n)$. Besides that, in the case$m=0$, the algorithm produces a pair of rational numbers$b_1,b_2\in\mathbb{Q}$such that inside the interval$(b_1,b_2)\subset\mathbb{R}$there is a unique real root$\omega\in(b_1,b_2)$of$\Phi$, herewith$l(b_1), l(b_2)\leqslant M\mathcal{P}((kd)^n)\$.

Full text: PDF file (1964 kB)

English version:
Journal of Soviet Mathematics, 1991, 55:2, 1519–1540

Bibliographic databases:

Document Type: Article
UDC: 519.5+512.46

Citation: N. N. Vorobjov (Jr.), D. Yu. Grigor'ev, “Solving systems of polynomial inequalities over real closed fields in subexponential time”, Computational complexity theory. Part 3, Zap. Nauchn. Sem. LOMI, 174, "Nauka", Leningrad. Otdel., Leningrad, 1988, 3–36; J. Soviet Math., 55:2 (1991), 1519–1540

Citation in format AMSBIB
\Bibitem{VorGri88} \by N.~N.~Vorobjov (Jr.), D.~Yu.~Grigor'ev \paper Solving systems of polynomial inequalities over real closed fields in subexponential time \inbook Computational complexity theory. Part~3 \serial Zap. Nauchn. Sem. LOMI \yr 1988 \vol 174 \pages 3--36 \publ "Nauka", Leningrad. Otdel. \publaddr Leningrad \mathnet{http://mi.mathnet.ru/znsl4510} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=0976172} \zmath{https://zbmath.org/?q=an:0683.65045} \transl \jour J. Soviet Math. \yr 1991 \vol 55 \issue 2 \pages 1519--1540 \crossref{https://doi.org/10.1007/BF01098273}