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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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}


Linking options:
  • http://mi.mathnet.ru/eng/znsl4510
  • http://mi.mathnet.ru/eng/znsl/v174/p3

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Записки научных семинаров ПОМИ
    Number of views:
    This page:81
    Full text:30

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019