Complexity of finding irreducible components of a semialgebraic set (Q1346599): Difference between revisions

Let \(W \subset \mathbb{R}^ n\) be a semialgebraic set determined by a Boolean combination of \(k\) atomic subformulas of the form \(f > 0\) or \(f = 0\), where the polynomials \(f \in \mathbb{Z} [X_ 1, \dots, X_ n]\), the degrees \(\deg_{X_ 1, \dots, X_ n} (f) < d\), and the maxima of bit lengths of coefficients \(l(f) < M\) for \(d\), \(M \in \mathbb{N}\). The author proposes an algorithm for producing the complexification, the Zariski closure and for finding all irreducible components of \(W\). An upper bound for the running time is \(M^{0(1)} (kd)^{n^{0(1)}}\). The procedure is applied to computing a Whitney system for a semialgebraic set and the real radical of a polynomial ideal.