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

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

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 3, Tome 174 (1988), pp. 3-36

Résumé

Let $\mathbb{Q}_m$ denote the field $\mathbb{Q}(\delta_1,\dots,\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,\dots,f_{k_1}>0, f_{k_1+1}\geqslant0,\dots,f_k\geqslant0 \qquad{(1)} $$ be the input system where polynomials $f_1,\dots,f_k\in\mathbb{Q}_m[X_1,\dots,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,\dots X_n)$ where polynomials $\alpha_1,\alpha_2\in\mathbb{Z}[\delta_1,\dots,\delta_m][X_1,\dots,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,\dots,\delta_m}(f_i)<d_0,\quad \mathrm{deg}_{X_1,\dots,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,\dots,h_t)$ for functions $h_1>0,\dots,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,\dots,\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,\dots,\delta_m,X_1,\dots,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)$.