Efficient algorithms for computing the euler-poincaré characteristic of symmetric semi-algebraic sets

Saugata Basu, Cordian Riener

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaChapterScientificvertaisarvioitu

2 Sitaatiot (Scopus)

Abstrakti

Let R be a real closed field and D ⊂ 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 Rk, which are defined by symmetric polynomials with coefficients in 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, are polynomially bounded in terms of 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-hardness) coming from discrete complexity theory.

AlkuperäiskieliEnglanti
OtsikkoContemporary Mathematics
KustantajaAmerican Mathematical Society
Sivut51-79
Sivumäärä29
Vuosikerta697
ISBN (elektroninen)978-1-4704-4222-4
ISBN (painettu)978-1-4704-2966-9
TilaJulkaistu - 2017
OKM-julkaisutyyppiA3 Kirjan tai muun kokoomateoksen osa

Sormenjälki

Sukella tutkimusaiheisiin 'Efficient algorithms for computing the euler-poincaré characteristic of symmetric semi-algebraic sets'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä