Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets
Saugata Basu, Cordian Riener · Contemporary mathematics - American Mathematical Society · 2017
Let R \mathrm {R} be a real closed field and D ⊂ R \mathrm {D} \subset \mathrm {R} an ordered domain. We consider the algorithmic problem of computing the generalized Euler-Poincaré characteristic of real algebraic as well as semi-algebraic subsets of R k \mathrm {R}^k , which are defined by symmetric polynomials with coefficients in D \mathrm {D} . We give algorithms for computing the generalized Euler-Poincaré characteristic of such sets, whose complexities measured by the number of arithmetic operations in D \mathrm {D} , are polynomially bounded in terms of k k and the number of polynomials in the input, assuming that the degrees of the input polynomials are bounded by a constant. This is in contrast to the best complexity of the known algorithms for the same problems in the non-symmetric situation, which are singly exponential. This singly exponential complexity for the latter problem is unlikely to be improved because of hardness result ( # P \#\mathbf {P} -hardness) coming from discrete complexity theory.