Finding connected components of a semialgebraic set in subexponential time (Q5966655): Difference between revisions

Let a semialgebraic set be given by a quantifier free formula of the first order theory of real closed fields with \(k\) atomic subformulas of type \(f \geq 0\), where the polynomials \(f\) have \(n\) variables, are of degree less than \(d\), with (integer) coefficients whose bit length is bounded by \(M\). The size of the semialgebraic set is then estimated by the bound \(L=Mkd^ n\). The main result in the paper is an algorithm that finds the connected components of the given semialgebraic set in time \(M^{0(1)}(kd)^{n^{0(1)}}\) (therefore it runs in subexponential time in terms of the size \(L)\). The number of components is less than \((kd)^{0(n)}\), and the output will be a certain quantifier free formula with less than \((kd)^{n^{0(1)}}\) atomic subformula of the type \(g \geq 0\) for each connected component, where \(g\) is a polynomial in \(n\) variables, of degree less than \((kd)^{n^{0(1)}}\) and coefficient bit lengths less than \(M(kd)^{n^{0(1)}}\). Actually, the results in the paper are formulated in a more general setting, namely allowing more general coefficients for the defining polynomials describing the semialgebraic set. The presented algorithms rely on much previous work, in particular requiring fast (subexponential- time) quantifier elimination and decidability algorithms of the theory of real closed fields, and algorithms for finding irreducible components of algebraic varieties over algebraically closed fields.